Najlepší spôsob, ako udávať zložitosť algoritmu, je samozrejme uviesť asymptoticky presný odhad, teda $\Theta$. Toto ale nemusí vždy byť možné. Existujú napríklad problémy, kde vieme dokázať nejaký horný odhad, ale nevieme, či je tesný. Navyše $O$ sa ľahšie píše a viac ľudí ho pozná. Preto sa veľmi často používa len $O$.
Nezabúdajme ale, že $O$ predstavuje len horný odhad a tých je vždy nekonečne veľa. Preto sa snažíme nájsť a udať čo najlepší z nich, t. j. čo najpomalšie rastúcu funkciu, ktorá zhora ohraničuje čas behu algoritmu.
Príklad 3. Máme utriedené pole $A$. Treba zistiť, či sa v ňom nachádzajú dva prvky s rozdielom $D$. Napísali sme na to nasledujúci program:
j = 0
for i in range(N):
while j<N-1 and A[i]-A[j] > D:
j++
if A[i]-A[j] == D
print("nachadza")
Je ľahké ukázať, že tento program je $O\left(N^2\right)$ – vnútorný cyklus sa
spustí $N$-krát a nikdy nespraví viac ako $N$ krokov. Ale poriadnejšia
analýza ukáže, že v skutočnosti tento program nie je kvadratický, ale
dokonca lineárny. Stačí si uvedomiť, že počas celého behu programu
sa príkaz "j++;" nemôže vykonať viac ako $N$-krát, a teda všetky
spustenia vnútorného cyklu dokopy spravia najviac $N$ krokov.
Keby sme teda o algoritme z Príkladu 3 povedali, že jeho časová zložitosť je $O\left(N^2\right)$, mali by sme pravdu. Ale viac informácie obsahuje presnejšie tvrdenie, že časová zložitosť tohto algoritmu je dokonca $O\left(N\right)$.