Какво е O-нотацията (Big O нотация)?

O-нотацията (Big O нотацията) е начин за описание на асимптотичната оценка на сложността на алгоритъм, тоест как времето за изпълнение или използването на памет се увеличава с увеличаването на размера на входните данни.

Например, ако алгоритъм има сложност O(n), това означава, че времето за изпълнение расте линейно с размера на входа. Ако е O(n²), времето расте пропорционално на квадрата на размера на входа.

Пример на Go:

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

Функцията sum има сложност O(n), тъй като преминава през всички елементи на масива веднъж.