Šta je O-notation (Big O notation)?

O-notation (Big O notation) je način za opisivanje asimptotske procene složenosti algoritma, odnosno kako vreme izvršavanja ili korišćenje memorije raste sa povećanjem veličine ulaznih podataka.

Na primer, ako algoritam ima složenost O(n), to znači da vreme izvršavanja raste linearno sa veličinom ulaza. Ako je O(n²), vreme raste proporcionalno kvadratu veličine ulaza.

Primer u Go:

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

Funkcija sum ima složenost O(n), jer prolazi kroz sve elemente niza jednom.