Majme dve funkcie f(n) a g(n). Piseme, ze f(n)=O(g(n)) pre n idúce nekonečna, a hovoríme, že "f(n) je veľké Ó od g(n) pre n idúce do nekonečna", ak pre všetky dostatočne veľké n a nejakú kladnú konštantu c platí |f(n)| < c|g(n)|.
Poznámka 1: Slová "pre n idúce do nekonečna" programátori zväcša nehovoria, lebo nikde inde ako v nekonečne ich funckie nezaujímajú.
Poznámka 2: Programátori používajú skoro vylúčne len kladné funkcie. Potom je absolútna hodnota v definícii je zbytočná.
Poznámka 3: Definícia zhruba hovorí, že funkcia f(n) nerastie rádovo viac ako funkcia g(n). Troška inak povedané, funkcia f(n) rastie najviac toľko ako nejaký násobok g(n). A ešte inak povedané, funckia f(n) je zhora ohraničená konštatným násobkom g(n).
Príklady:
Poznámka 4: Voľne povedané, funckie sú O-notáciou usporiadané podľa toho, ako rýchlo rastú. Nie je odveci mať približný prehľad o tom, ako rýchlo ktoré funkcie rastú.
Časovou zložitosťou voláme to, ako dlho program beží v závislosti od počtu dát, ktoré do neho nasypeme.
Oboje, čas aj počet dát sa tažko meria. Čas zväčša meriame v počte elementárnych operácií, ktoré program urobí. Veľkosť dát zase meriame počtom bajtov vstupu, prípadne parametrom n uvedenom v zadaní úlohy.
Kedže ani jedno ani druhé nevieme presne merať ani vypočítať, používame O-notáciu. Daľej, nás skoro vždy zaujíma len najhorší prípad, na ktorom program najdlhšie beží.
Takže sa zásadne obmedzujeme na konštatovanie, že náš program nikdy nebeží dhlšie ako nejaký konštatný násobok funkcie g(n). Tento fakt zapisujeme takto: "Náš program ma časovú zložitosť O(g(n))".