Už vieš, že O-notácia nám hovorí o hornej hranici časovej zložitosti algoritmu. To znamená, že ak má algoritmus zložitosť $O(n)$, potom vieme, že v najhoršom prípade nebude trvať dlhšie ako konštantný násobok $n$. Je to niečo ako "maximálny čas", ktorý môže trvať.
Okrem O-notácie sa využívajú ešte ďalšie dve:
Notácia $\Omega$ nám hovorí o dolnej asymptotickej hranici časovej zložitosti algoritmu. Ak má algoritmus zložitosť $\Omega(n)$, znamená to, že čas vykonania algoritmu bude rásť aspoň tak rýchlo ako $n$. Inými slovami, algoritmus nebude asymptoticky rýchlejší ako $n$.
Notácia $\Theta$ nám hovorí o presnej (tesnej) hranici časovej zložitosti algoritmu. Ak má algoritmus zložitosť $\Theta(n)$, znamená to, že horná aj dolná asymptotická hranica jeho časovej zložitosti je $n$. Inými slovami, algoritmus bude trvať približne konštantný násobok $n$.
Ak je zložitosť algoritmu $\Theta(n)$, potom platí, že algoritmus je zároveň $O(n)$ aj $\Omega(n)$. To znamená, že algoritmus nebude asymptoticky pomalší ako $n$ a ani asymptoticky rýchlejší ako $n$. Vyjadruje skutočné správanie algoritmu pre veľké vstupy.