Big-O en Python para entrevistas — el coste de listas, dicts y sets

En una entrevista técnica, después de resolver el ejercicio, casi siempre llega la misma pregunta: “¿y qué complejidad tiene?”. Mucha gente que programa bien se queda en blanco aquí, no porque sea difícil, sino porque nunca se lo explicaron sin fórmulas.

Vamos a arreglarlo. Big-O sin matemáticas, y la tabla de costes de listas, diccionarios y sets en Python que de verdad te van a preguntar.

Esto es el complemento natural de los patrones de coding interview: elegir el patrón correcto es, en el fondo, elegir la estructura con el coste adecuado.

Big-O en un minuto (sin fórmulas)

Big-O responde a una pregunta: si los datos crecen, ¿cuánto crece el trabajo? No mide segundos; mide cómo escala.

• O(1) — constante: el trabajo no cambie aunque haya 10 o 10 millones de elementos. Acceder a lista[5] o a dic["clave"].
• O(n) — lineal: el trabajo crece igual que los datos. Recorrer una lista con un for.
• O(n²) — cuadrática: crece con el cuadrado. Un bucle dentro de otro sobre los mismos datos. Se vuelve lento rápido.
• O(log n) — logarítmica: crece muy despacio. Búsqueda binaria sobre datos ordenados.

La intuición que vale en la entrevista: cuenta los bucles anidados. Un bucle, O(n). Dos anidados sobre los mismos datos, O(n²). Y desconfía del in sobre una lista dentro de un bucle (es un bucle escondido).

El coste de las operaciones de list

nums = [3, 1, 4, 1, 5]

nums[2]          # O(1)  acceso por índice
nums.append(9)   # O(1)  añadir al final
nums.pop()       # O(1)  quitar del final
nums.insert(0, 0)# O(n)  desplaza todo a la derecha
nums.pop(0)      # O(n)  desplaza todo a la izquierda
x in nums        # O(n)  recorre hasta encontrar
nums.sort()      # O(n log n)

La trampa clásica: insert(0, ...) y pop(0) parecen inocentes pero son O(n) porque hay que mover todos los demás elementos. Si necesitas meter/sacar por delante mucho, usa collections.deque (O(1) por ambos extremos).

El coste de dict y set (y por qué son O(1))

d = {"a": 1, "b": 2}
d["a"]           # O(1)  acceso por clave
d["c"] = 3       # O(1)  insertar
"a" in d         # O(1)  pertenencia

s = {1, 2, 3}
s.add(4)         # O(1)
2 in s           # O(1)  pertenencia

¿Por qué O(1)? Porque son tablas hash: la clave se pasa por una función hash que calcula directamente dónde está, sin recorrer nada. Por eso las claves de un diccionario y los elementos de un set deben ser hashables (inmutables): una lista no puede ser clave, una tupla sí.

Nota honesta para la entrevista: es O(1) amortizado. En el peor caso teórico (muchas colisiones de hash) puede degradarse, pero en la práctica se considera O(1). Mencionarlo demuestra que entiendes lo que dices.

El ejemplo que lo cambia todo: in sobre lista vs set

Este es el caso que más se pregunta porque es el más práctico:

# Tienes una lista de IDs permitidos y compruebas muchos accesos
permitidos = list(range(1_000_000))      # lista
# permitidos = set(range(1_000_000))     # set

for acceso in muchos_accesos:
    if acceso in permitidos:             # lista: O(n) cada vez
        ...                              # set:   O(1) cada vez

Con la lista, cada in recorre hasta un millón de elementos. Con el set, va directo. Si haces esa comprobación miles de veces, es la diferencia entre minutos y milisegundos. La regla: si vas a comprobar pertenencia más de un par de veces sobre datos grandes, convierte a set primero.

Tabla resumen para memorizar

Errores de complejidad que descartan candidatos

• Concatenar strings en un bucle con +=: cada concatenación crea un string nuevo → O(n²). Usa "".join(lista).
• x in lista dentro de un for: es un O(n²) disfrazado. Pásalo a set.
• Decir “rápido” o “lento” en vez de la complejidad. El entrevistador quiere O(algo).
• Olvidar el espacio. También se pregunta la complejidad en memoria: un diccionario auxiliar añade O(n) de espacio.

Cómo decirlo en la entrevista

Al terminar el ejercicio, una frase tipo: “Es O(n) en tiempo porque recorro la lista una vez, y O(n) en espacio por el diccionario que uso para guardar lo visto.” Eso, dicho con naturalidad, transmite más seniority que el propio algoritmo.

Si quieres practicar el “decirlo en voz alta” sin trabarte, lo tienes en cómo explicar tu código en una entrevista técnica.

En resumen

Big-O no es matemáticas: es “¿cuánto crece el trabajo si crecen los datos?”. Cuenta bucles, recuerda que dict y set dan O(1) frente al O(n) de buscar en una lista, y evita los O(n²) escondidos (in sobre lista en bucle, += de strings). Llévate el cheatsheet del clúster con la tabla para el día antes.

Y si quieres dominar Python de verdad —estructuras de datos, rendimiento y proyectos reales, no solo trucos para la entrevista— ese es el camino del curso.