Co je to O-notation (Big O notation)?

O-známka (Big O notace) je způsob popisu asimptotického odhadu složitosti algoritmu, tj. jak se zvyšuje doba běhu nebo využití paměti s růstem velikosti vstupních dat.

Například, pokud má algoritmus složitost O(n), znamená to, že doba běhu roste lineárně s velikostí vstupu. Pokud je O(n²), roste úměrně druhé mocnině velikosti vstupu.

Příklad v Go:

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

Funkce sum má složitost O(n), protože projde všechny prvky pole jednou.