Složitost algoritmu měříme jako funkci závislou na vstupu algoritmu. Když algoritmy analyzujeme tak postupujeme

  1. Zjistíme jak vlastně změřit vstup, jsou-li vstupem dvě čísla tak třeba zda se hodí algoritmus odvíjet od jejich maxima, či třeba počtu cifer, atd.
  2. Určíme maximální možný počet elementárních operací provedených na vstupu velikosti , pokud nedokážeme určit přesný počet, tak se snažíme o co nejtěsnější horní odhad.
  3. Z odebereme všechny části polynomu, až na nejrychleji rostoucí člen.
  4. Z odebereme multiplikativní konstanty. Postupem nám zbude jen jakási funkce a řekneme, že algoritmus je asymptoticky složitý, tedy v nejhorším případě mu roste složitost pomocí funkce.

Můžeme též zavést průměrnou časovou složitost, kdy vezmeme vstupy velikosti a analyzujeme kolik zdrojů (výpočetního času) spotřebuje v průměru.

Asymptotické složitostí třídy se dají měřit také pro prostorovou složitost a pro její zjištění se dá stejně jako v úvodním postupu, jen nahradíme elementární operace za využité triviální prostorové buňky.


Asymptotická notace

Definice: Nechť jsou funkce, řekneme že , tedy patří do složitostní třídy , když platí pro skoro všechny vstupy (existuje jen konečně mnoho výjimek.)

Definice: Mějme , pokud taková, že pro skoro všechna , tak řekneme, že , a je asymptotický dolní odhad funkce .

Definice: Pokud pro platí a , pak je třídy . Tedy .