Pod odhadom časovej zložitosti rozumieme odhad času, ktorý bude program trvať, v závislosti od vstupných premenných. Tento čas je priamo úmerný počtu elementárnych operácií, ktoré program vykonáva - priradenie jednoduchej premennej, porovnanie jednoduchých premenných, aritmetické operácie, atď. Väčšinou sa zaujímame o to, ako dlho beží program v priemernom, alebo najhoršom prípade (čiže si všímame priemerný, alebo maximálny čas vykonávania programu). Analogicky odhad pamäťovej zložitosti je odhad veľkosti použitej pamäti v bajtoch v závislosti od vstupných premenných.

Väčšinou nás nezaujímajú presné hodnoty (niekto má rýchlejší počítač, na niektorých počítačoch má integer 2 a na iných 4 bajty a pod.), preto používame tzv. \(O\)-notáciu. Hovoríme, že funkcia \(f(n)\) (napr. čas behu programu v milisekundách v závislosti od veľkosti vstupu \(n\)) je \(O(g(n))\) (\(g(n)\) je tiež funkcia), ak existuje taká konštanta \(c\), že pre všetky dostatočne veľké \(n~(n>n_0)\) je \(f(n) \leq c \cdot g(n)\).

Napríklad, ak program pre vstup veľkosti \(n\) nebeží nikdy viac ako \(T(n)=\frac{1}{2}n^3 + 5n\log(n) + 83\) mikrosekúnd, môžeme povedať, že má časovú zložitosť \(O(n^3)\). Ak program potrebuje najviac \(M(n) = 3n\log_2(n) + 150n + 15\) bajtov pamäti, povieme, že má pamäťovú zložitosť \(O(n\log(n))\). (Poznamenávame, že ak je nejaká funkcia \(O(n^2)\), tak je aj \(O(n^3)\)) atď. Vždy sa však snažíme nájsť čo najmenšie horné ohraničenie, t.j. funkciu, ktorá čo najpomalšie rastie.)

Niekoľko príkladov (v pseudokóde)

sucet = 0
for i in 1..n:
    for j in 1..m:
        for k in 1..j:
            sucet = i+j+k

Predchádzajúci program má časovú zložitosť \(O(n\cdot m^2)\). Posledný riadok programu sa vykoná \( \frac{1}{2} n \cdot m(m+1)\)-krát.

nacitaj n cisel do pola A
b = 0 
e = n
while e-b > 1:
    m = (b+e)/2
    pocet = 0
    for i in 1..n:
        if A[i] < m: pocet += 1
    if pocet > n/2: e = m
    else: b = m

Predchádzajúci program má časovú zložitosť \(O(n\log(n))\). Vnútro while-cyklu sa vykoná \(O(n\log n)\)-krát, pretože \((e-b)\) sa po každom kroku zmenší na polovicu. Vnútro while-cyklu má časovú zložitosť \(O(n)\).