Notación Big-O: expresando el rendimiento con números

Al finalizar este tema

Comprenderás qué es la notación Big-O, podrás estimar la complejidad temporal al analizar código y explicarás las diferencias entre O(1), O(n), O(n²) y O(log n).

¿Por qué es necesaria la notación Big-O?

"Este código es lento". Debes poder decir qué tan lento es y cuánto más se ralentizará a medida que aumenten los datos. La notación Big-O es la forma de expresar cómo aumenta el número de operaciones según el tamaño de la entrada (n).

No se trata de medir el tiempo de ejecución en segundos, ya que esto varía según el rendimiento del ordenador. La notación Big-O describe el patrón de crecimiento.

O(1): tiempo constante

El tiempo requerido es siempre el mismo, independientemente del tamaño de la entrada.

def get_first(items):
    return items[0]  # 1 o 1 millón, siempre 1 vez

# La búsqueda en diccionario también es O(1)
user = {"name": "Kim Hun"}
user["name"]  # Cálculo de hash → acceso directo

Aunque los datos aumenten diez veces, el tiempo permanece constante.

O(n) — Tiempo lineal

El tiempo aumenta proporcionalmente al tamaño de la entrada.

def find_max(items):
    max_val = items[0]
    for item in items:      # n iteraciones
        if item > max_val:
            max_val = item
    return max_val

Si la lista tiene 100 elementos, se realizan 100 comparaciones; si tiene 1 millón, se realizan 1 millón de comparaciones. Si los datos aumentan 10 veces, el tiempo también aumenta 10 veces. Un bucle for que recorre la totalidad de los elementos suele tener una complejidad de O(n).

O(n²) — Complejidad cuadrática

El ejemplo típico son los bucles anidados.

def has_duplicate(items):
    for i in range(len(items)):         # n veces
        for j in range(i + 1, len(items)):  # máximo n veces
            if items[i] == items[j]:
                return True
    return False

Si tenemos 100 elementos, son aproximadamente 5.000 veces; con 1.000 elementos, unas 500.000; y con 10.000 elementos, cerca de 50.000.000. Si los datos aumentan 10 veces, el tiempo aumenta 100 veces. Esta es la razón por la que O(n²) es peligroso.

# Mejora a O(n) usando set
def has_duplicate_fast(items):
    seen = set()
    for item in items:       # n veces
        if item in seen:     # Búsqueda en set O(1)
            return True
        seen.add(item)
    return False

Al resolver el mismo problema con O(n), el número de operaciones se reduce de 50 000 000 (para 10 000 elementos) a solo 10 000.

O(log n) — Tiempo logarítmico

En cada paso, el rango de búsqueda se reduce a la mitad. Un ejemplo representativo es la búsqueda binaria.

def binary_search(sorted_list, target):
    low, high = 0, len(sorted_list) - 1

    while low <= high:
        mid = (low + high) // 2
        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            low = mid + 1        # Descartar la mitad izquierda
        else:
            high = mid - 1       # Descartar la mitad derecha

    return -1  # No encontrado

En un conjunto de 1 millón de elementos, se encuentra en un máximo de 20 comparaciones (log₂(1.000.000) ≈ 20). Si fuera O(n), serían 1 millón de comparaciones; con O(log n), son solo 20. Sin embargo, esto solo funciona con datos ordenados.

Comparación visual

O(n²) no es práctico incluso cuando n supera los 10.000. O(n log n) es la complejidad de los algoritmos de ordenamiento eficientes (merge sort, quick sort).

Reglas clave para leer Big-O

1. Se ignoran las constantes: O(3n) = O(n), O(100) = O(1)
2. Se ignoran los términos de menor orden: O(n² + n) = O(n²) — cuando n es grande, n² domina a n
3. Se considera el peor caso: Al buscar en una lista, si el elemento está al principio es O(1), pero Big-O se basa en el peor escenario (que esté al final), que es O(n)

Con estas 3 reglas, puedes estimar la complejidad Big-O de la mayoría del código.

Resumen clave

Big-O es una herramienta para determinar: "¿este código sobrevivirá si los datos aumentan 10 veces?". Es más importante reconocer patrones que realizar cálculos exactos: un bucle for simple es O(n), bucles anidados son O(n²) y reducir a la mitad en cada paso es O(log n). Aunque es un tema frecuente en entrevistas, su utilidad real en el trabajo es identificar la causa de por qué "una API se vuelve lenta cuando hay muchos datos".