Ce este notația O (notația Big O)?

Notatia O (notatia Big O) este o metodă de a descrie evaluarea asimptotică a complexității unui algoritm, adică modul în care timpul de execuție sau utilizarea memoriei crește odată cu creșterea dimensiunii datelor de intrare.

De exemplu, dacă un algoritm are o complexitate O(n), înseamnă că timpul de execuție crește liniar odată cu dimensiunea intrării. Dacă are O(n²), timpul crește proporțional cu pătratul dimensiunii intrării.

Exemplu în Go:

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

Funcția sum are o complexitate O(n), deoarece parcurge toate elementele array-ului o dată.