Nech $f$, $g$ sú kladné neklesajúce funkcie definované na množine prirodzených čísel. (Všimni si, že naše funkcie udávajúce presnú časovú zložitosť tieto vlastnosti majú.) Hovoríme, že $f\left( N \right)$ je $O\left( g\left( N \right)\right)$ (čítaj: $f$ je (veľké) $O$ (od) $g$) ak pre nejaké konštanty $c$ a $N_0$ platí nasledujúca podmienka:
$$\forall N > N_0: f\left( N \right)< c\cdot g\left( N \right)$$
Preložené do ľudskej reči, $f\left( N \right)$ je $O\left( g\left( N \right)\right)$, ak pre nejaké $c$ skoro celý graf funkcie $f$ leží pod grafom funkcie $c \cdot g$. Všimni si, že toto znamená, že $f$ rastie nanajvýš tak rýchlo ako $c \cdot g$.
Namiesto "$f\left( N \right)$ je $O\left( g\left( N \right)\right)$" väčšinou píšeme $f(N) = O(g(N))$. Pozor, táto rovnosť nie je symetrická – zápis "$O\left( g\left( N \right)\right)= f\left( N \right)$" nemá zmysel a " $g\left( N \right)= O\left( f\left( N \right)\right)$" nie je ekvivalentné tvrdenie. (Ak ťa to pletie, predstav si, že $O\left( g\left( N \right)\right)$ je množina funkcií, ktoré rastú nanajvýš tak rýchlo ako $g$ a namiesto $=$ si predstav znak $\in$.)
To, čo sme práve definovali, sa volá $O$-notácia. Jedno jej bežné použitie je udávanie horných odhadov časovej zložitosti algoritmov.
Uvažujme napríklad funkciu $f(N) = \frac{3N(N - 1)}{2} + N = 1.5N^2 - 0.5N$ z Príkladu 2. Podľa našej definície je $f\left( N \right)= O\left( N^2 \right)$. (Jedna možnosť, ako zvoliť potrebné konštanty, je $c = 2$ a $N_0 = 0$.) Toto znamená, že $f$ rastie (asymptoticky) najviac tak rýchlo ako $N^2$.
A toto je práve to dôležité, čo o našej funkcii potrebujeme vedieť. Vieme totiž vyvodiť nasledujúci dôležitý záver: Keď zdvojnásobíme veľkosť vstupu, zväčší sa čas behu nášho programu najviac na rádovo štvornásobok. Bez ohľadu na to, aký rýchly počítač máme a aká je konkrétna funkcia $f$, takáto úvaha bude vždy fungovať.
Budeme teda $O$-notáciu používať na zápis časovej zložitosti algoritmov (a tiež na zápis ich pamäťovej zložitosti, t. j. veľkosti použitej pamäte v závislosti od veľkosti vstupu). Napr. pre algoritmus z Príkladu 2 môžeme povedať: "Časová zložitosť tohto algoritmu je $O\left( N^2 \right)$" alebo stručnejšie "Tento algoritmus je $O\left( N^2 \right)$".
Podobne ako sme definovali $O$ môžeme definovať aj $\Omega$ a $\Theta$.
Hovoríme, že $f\left( N \right)$ je $\Omega\left( g\left( N \right)\right)$ ak $g\left( N \right)= O\left( f\left( N \right)\right)$, inými slovami, ak $f$ rastie aspoň tak rýchlo ako $g$.
No a hovoríme, že $f\left( N \right)= \Theta\left( g\left( N \right)\right)$ ak $f(N) = O(g(N))$ a $g\left( N \right)= O\left( f\left( N \right)\right)$, inými slovami, ak obe funkcie rastú rádovo rovnako rýchlo.
Malo by byť jasné, že zatiaľ čo $O$ udávalo horný odhad funkcie, $\Omega$ udáva dolný odhad a $\Theta$ sa bude používať na udanie asymptoticky presného odhadu. Sú aj ďalšie podobné značenia (napr. pre ostré nerovnosti), ale s týmito tromi si nejakú dobu vystačíme.