Uvedomme si, že počet elementárnych operácií programu sa dá vyjadriť ako funkcia od premenných na vstupe. Ak máme na vstupe číslo $n$, bude to funkcia tohto čísla. A my chceme nejak porovnávať tieto funkcie. Dobrá miera na porovnávanie je schopnosť rásť. Čím rýchlejšie funkcia rastie, tým viac operácií bude treba. Takisto nás poväčšine nezaujímajú malé vstupy, ale také, na ktorých zrátanie treba milióny operácií. A samozrejme, nechceme byť zbytočne presný. Však $1\,000\,000$ a $1\,000\,042$ je skoro to isté. Hore dole $42$ operácií, také niečo môžeme zanedbať.
A na toto všetko je vytvorená takzvaná $O$-notácia a asymptotické určovanie zložitosti. Hneď vás varujem. Nasledujúce odseky budú obsahovať nejaké formálne definície aj niektoré neformálne tvrdenia. Ono je to celé veľmi intuitívne a keď s tým začnete pracovať, rýchlo si na to zvyknete. Môže to byť však zo začiatku trochu mätúce, pokúsim sa vám to však podať čo najlepšie.
Začnime s príkladom. Majme program, ktorý vykoná $f(n) = n^2/2 + 5n + 4$. Prvé pravidlo znie, že konštanty zanedbáme. To, či urobíme operácií $n$ alebo $5n$ je skoro jedno, zdvihne sa to len o konštantu, ktorá nezávisí od veľkosti vstupu. Zrazu máme teda $f'(n) = n^2 + n$. Druhé pravidlo zase hovorí o tom, že nás zaujíma len najväčší člen funkcie, teda ten, čo najrýchlejšie rastie. V tomto prípade $n^2$ rastie oveľa rýchlejšie ako $n$. Tým pádom dostaneme výslednú funkciu $f''(n) = n^2$. A to je náš odhad na to, koľko operácii spraví náš program.
Možno sa to zdá hrubé, koľko vecí sme zanedbali, ale ono to vôbec nie je tak. Tých zanedbaných vecí je najviac konštantne viac ako to čo nám zostalo. A to nám stačí. Samozrejme takýto spôsob škrtania je škaredý a tieto dve pravidlá sú len pomôcky. Potrebujeme jasnú definíciu a tou je už spomínaná $O$-notácia.
Definícia: Majme dve funkcie $f$ a $g$. Hovoríme, že $f \in O(g)$, ak existuje $n_0$ a $c>0$ také, že pre všetky $n \geq n_0$ platí $|f(n)|\leq c|g(n)|$.
A slovami: Hovoríme, že funkcia $f$ patrí do $O(g)$ (všimnite si, že $O(g)$ je množina všetkých funkcií, pre ktoré platí daná vlastnosť), ak existujú také konštanty $n_0$ a $c$, že pre dosť veľké $n$ (lebo $n \geq n_0$) je $c|g(n)|$ (absolútna hodnota) väčšia ako $f(n)$.
Teraz už ľahko určíme, že naozaj naše $f(n) = n^2/2 + 5n +4 = O(n^2)$ (tento zápis síce nie je úplne korektný, lebo $O(n^2)$ je množina, napriek tomu sa často používa). Stačí, ak si zvolíme $n_0=10$ a $c=2$. Ľahko potom nahliadneme, že $n^2/2 + 5n + 4 \leq 2n^2$, lebo toto je vlastne $5n + 4 \leq 3n^2/2$. Táto nerovnosť pre $n=10$ platí a ďalej bude už len masívne narastať.
Tiež si všimnite, že napríklad $n^3 \notin O(n^2)$. Ak si zvolíte totiž ľubovoľné $c$, tak $n^3$ je väčšie od $cn^2$ pre všetky $n\geq c$. Naopak však platí, že $n^2 \in O(n^3)$, lebo to vyhovuje definícii pre $c=n_0=1$.