¿Qué es la notación O (notación Big O)?

La notación O (notación Big O) es una forma de describir la evaluación asintótica de la complejidad de un algoritmo, es decir, cómo crecen el tiempo de ejecución o el uso de memoria con el aumento del tamaño de los datos de entrada.

Por ejemplo, si un algoritmo tiene una complejidad O(n), significa que el tiempo de ejecución crece linealmente con el tamaño de la entrada. Si es O(n²), el tiempo crece proporcional al cuadrado del tamaño de la entrada.

Ejemplo en Go:

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

La función sum tiene una complejidad O(n), ya que recorre todos los elementos del array una vez.