Matematické Fórum

Je třeba si ten algoritmus představit jako rozhodovací strom. Výsledkem každého porovnání je buď ano, nebo ne, čili ten strom bude binární (ale to je vlastně jedno). Důležité je si uvědomit, kolik ten strom bude mít listů, tj. kolik existuje různých konečných uspořádání těch prvků. Je to právě počet všech permutací na n prvcích, takže n!. Teď předpokládejme, že algoritmus dokáže pro každý vstup vybrat ten správný list. Kolik musel udělat porovnání v nejhorším případě? Tolik, kolik je pater ve stromu, tedy , zaokrouhleno nahoru.
Nakonec stačí použít třeba odhad, že a použít všechny vlastnosti logaritmu.

↑ panak:
To se dá. Ten poslední řádek je návod jak zdůvodnit proč se to dá. Ta nerovnost tam jde dokázat indukcí, ale postačí skoro jakákoliv slabší nerovnost pro faktoriál.