Notación Big O: cómo medir la eficiencia de un algoritmo

La notación Big O es el lenguaje universal para hablar de eficiencia en programación. No importa qué lenguaje uses ni qué hardware tengas — Big O te dice cómo escala un algoritmo cuando los datos crecen.

Qué mide Big O

Big O describe el comportamiento de un algoritmo en el peor caso a medida que el tamaño de la entrada (n) crece hacia el infinito. No mide segundos — mide operaciones. O(n) no significa "tarda n segundos", sino "el número de operaciones crece linealmente con n".

Las complejidades más comunes

O(1) — constante: acceder a un elemento de un array por índice. No importa cuántos elementos tenga.
O(log n) — logarítmica: búsqueda binaria. Con 1.000 elementos, ~10 pasos; con 1.000.000, ~20 pasos.
O(n) — lineal: buscar el máximo en un array no ordenado. Hay que mirar cada elemento.
O(n log n) — linealítmica: Mergesort, Quicksort. El mejor posible para ordenación por comparación.
O(n²) — cuadrática: dos bucles anidados. Burbuja, selección. Se vuelve inutilizable con n > 10.000.
O(2ⁿ) — exponencial: fuerza bruta en problemas combinatorios. Solo viable para n muy pequeño.

Cómo calcular el Big O de tu código

Regla general: un bucle simple = O(n). Dos bucles anidados = O(n²). Dividir el problema a la mitad en cada paso = O(log n). Combinar división y bucle = O(n log n). Ignora constantes multiplicativas y términos menores — O(3n + 5) = O(n).

Preguntas frecuentes

¿Big O mide el peor caso siempre?

Por defecto sí, aunque existen también la notación Omega (mejor caso) y Theta (caso promedio). En entrevistas y análisis práctico, Big O = peor caso.

¿O(n log n) es siempre mejor que O(n²)?

Asintóticamente sí. Pero para n pequeño (menos de ~50 elementos), un O(n²) simple puede ser más rápido por el menor overhead.