Czym jest notacja O (notacja Big O)?

Notacja O (notacja Big O) to sposób opisu asymptotycznej oceny złożoności algorytmu, czyli tego, jak czas wykonania lub zużycie pamięci rośnie wraz z zwiększeniem rozmiaru danych wejściowych.

Na przykład, jeśli algorytm ma złożoność O(n), oznacza to, że czas wykonania rośnie liniowo wraz z rozmiarem wejścia. Jeśli O(n²), czas rośnie proporcjonalnie do kwadratu rozmiaru wejścia.

Przykład w Go:

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

Funkcja sum ma złożoność O(n), ponieważ przechodzi przez wszystkie elementy tablicy raz.