Odhad počtu operácií

Teraz, keď vieme počítať elementárne operácie, je jasné, prečo je Program 1 najrýchlejší. Ten potrebuje len pár operácií, bez ohľadu na to, aké veľké je n. A aj medzi Programom 2 a Programom 3 je jasné, ktorý je lepší.

Ale čo ak máme dva programy, ktoré pre vstup veľkosti $n$ urobia:

• Program A: $20n$ operácií
• Program B: $n^2$ operácií

Ktorý z nich je rýchlejší?

• Pre malé $n$, napríklad 10 je program B rýchlejší, lebo spraví iba $100$ operácií, zatiaľ čo program A ich spraví až $200$.
• Pre väčšie $n$, napríklad 30 sa však ukáže, že program A bude rýchlejší, lebo spraví iba $300$ operácií, zatiaľ čo program A ich spraví až $900$.

Intuitívne cítime, že program A je celkovo lepší, pretože pre väčšinu vstupov je rýchlejší. A práve takýto odhad - závislosť počtu operácií od vstupu - nazývame časovou zložitosťou algoritmu.

Nie je to síce úplne presné číslo, ale dáva nám to dôležité informácie. Napríklad, ak vieme, že program vykoná $n^2$ operácií a pre vstup $n=200$ trvá 1s, tak pre vstup $n=400$ bude trvať rádovo 4 sekundy. Veľkosť sa nám síce zdvojnásobila, ale beh bude trvať 4-krát dlhšie!