O que é a notação O (notação Big O)?

A notação O (notação Big O) é uma forma de descrever a avaliação assintótica da complexidade de um algoritmo, ou seja, como o tempo de execução ou o uso de memória aumenta com o aumento do tamanho dos dados de entrada.

Por exemplo, se um algoritmo tem complexidade O(n), isso significa que o tempo de execução cresce linearmente com o tamanho da entrada. Se for O(n²), o tempo cresce proporcional ao quadrado do tamanho da entrada.

Exemplo em Go:

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

A função sum tem complexidade O(n), pois percorre todos os elementos do array uma vez.