Wat is de O-notatie (Big O-notatie)?

O-notatie (Big O-notatie) is een manier om de asymptotische beoordeling van de complexiteit van een algoritme te beschrijven, dat wil zeggen hoe de uitvoeringstijd of het geheugenverbruik groeit met de toename van de invoergegevens.

Bijvoorbeeld, als een algoritme een complexiteit van O(n) heeft, betekent dit dat de uitvoeringstijd lineair toeneemt met de grootte van de invoer. Als het O(n²) is, groeit de tijd evenredig met het kwadraat van de invoergrootte.

Voorbeeld in Go:

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

De functie sum heeft een complexiteit van O(n), omdat hij alle elementen van de array één keer doorloopt.