Čo je O-notation (Big O notation)?

O-notation (Big O notation) je spôsob, ako popísať asymptotické odhady zložitosti algoritmu, teda ako rastie čas vykonávania alebo využitie pamäte s rastom veľkosti vstupných dát.

Napríklad, ak má algoritmus zložitosť O(n), znamená to, že čas vykonávania rastie lineárne s veľkosťou vstupu. Ak je O(n²), čas rastie úmerne štvorcu veľkosti vstupu.

Príklad v Go:

func sum(arr []int) int {
    total := 0
    for _, v := range arr {
        total += v
    }
    return total
}

Funkcia sum má zložitosť O(n), pretože prechádza všetky prvky poľa raz.