Cos'è la notazione O (notazione Big O)?

La notazione O (notazione Big O) è un modo per descrivere la valutazione asintotica della complessità di un algoritmo, cioè come il tempo di esecuzione o l’utilizzo della memoria cresce con l’aumentare delle dimensioni dei dati di input.

Ad esempio, se un algoritmo ha una complessità O(n), significa che il tempo di esecuzione cresce linearmente con la dimensione dell’input. Se è O(n²), il tempo cresce proporzionalmente al quadrato della dimensione dell’input.

Esempio in Go:

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

La funzione sum ha una complessità O(n), poiché attraversa tutti gli elementi dell’array una volta.