What is O-notation (Big O notation)?

O-notation (Big O notation) is a way of describing the asymptotic estimate of an algorithm's complexity, that is, how the execution time or memory usage grows with an increase in input data size.

For example, if an algorithm has a complexity of O(n), it means that the execution time grows linearly with the input size. If it's O(n²), the time grows proportionally to the square of the input size.

Example in Go:

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

The sum function has a complexity of O(n) because it iterates over all elements of the array once.