📈 Complejidad Big-O

drag the slider — every mode updates live

Pruébalo: Arrastra el deslizador N desde 4 hasta 4k, presionando ejecutar experimento en cada parada. En N=4 todas las barras se ven iguales; en N=4k la barra O(n²) empequeñece a las demás. Esa brecha es justo lo que Big-O intenta advertirte.

Por qué importa

Cada estructura de datos que verás en las próximas 10 lecciones cambia un costo por otro. Los arreglos leen en O(1) pero insertan en O(n). Las tablas hash buscan en O(1) pero no tienen orden. Los árboles balanceados sacrifican algo de velocidad en el factor constante para garantizar el peor caso en O(log n). Ninguna de esas palabras significa nada hasta que hayas sentido cómo se ve la diferencia a medida que N crece.

Para eso sirve esta lección. Todavía sin código — solo la curva.

Qué mide Big-O

La cantidad de operaciones básicas que realiza un algoritmo, en función del tamaño de la entrada, en el peor caso, ignorando constantes y términos de orden inferior.

Tres piezas fundamentales:

• En función del tamaño de la entrada. Es una curva, no un número. "¿Cuántas comparaciones tomó esto?" no tiene respuesta; "¿Cuántas comparaciones tomó esto para N elementos?" sí la tiene.
• Peor caso. Una búsqueda lineal entre 1.000 elementos podría encontrar el objetivo en el primer intento. Pero si vas a llevar ese código a producción, tienes que planear para lo peor — revisar los 1.000.
• Ignorando constantes y términos de orden inferior. 3n + 5 y n son ambos O(n). Las constantes se diluyen a medida que N crece. Importan para los benchmarks; no importan para la forma asintótica.

O, Θ, Ω — las tres cotas

Los ingenieros dicen "Big-O" de manera informal, pero los libros de texto distinguen tres notaciones. Describen diferentes cotas sobre el crecimiento de una función.

Notaciones asintóticas

O(f(n)) — cota superior. T(n) = O(f(n)) significa que T crece a lo sumo tan rápido como f. "No cuesta más que."

Ω(f(n)) — cota inferior. T(n) = Ω(f(n)) significa que T crece al menos tan rápido como f. "No cuesta menos que."

Θ(f(n)) — cota ajustada. Tanto O(f(n)) como Ω(f(n)). "Cuesta exactamente proporcional a."

Un ejemplo concreto — merge sort

O(n log n) — su peor caso no es peor que n log n. Cierto pero poco preciso: también es O(n²), O(n³), … cualquier cota superior se cumple.

Ω(n log n) — su mejor caso es al menos n log n (cualquier ordenamiento por comparación tiene esta cota inferior por un argumento de teoría de la información).

Θ(n log n) — la afirmación ajustada: merge sort es exactamente del orden de n log n, ni más rápido ni más lento.

Por qué esto importa al repasar: cuando un libro de texto escribe Θ(n) está afirmando que el algoritmo está acotado tanto superior como inferiormente por n — eso es una afirmación más fuerte que O(n). Una búsqueda binaria es O(log n) (peor caso), Ω(1) (mejor caso — acierto en la primera prueba), y no es Θ(log n) en general — pero sí Θ(log n) en el peor caso. Define de qué caso estás hablando antes de elegir una notación.

Mejor, peor, promedio

De la mano de las cotas anteriores está qué entrada mides:

• Peor caso — la entrada que maximiza el trabajo. El predeterminado cuando dices "Big-O" sin aclarar.
• Mejor caso — la entrada que minimiza el trabajo. El mejor caso de quicksort es Θ(n log n); el peor es Θ(n²).
• Caso promedio — el trabajo esperado sobre una distribución de entradas. La búsqueda en una tabla hash es O(1) en promedio pero O(n) en el peor caso.
• Amortizado — el promedio sobre una secuencia de operaciones en la misma estructura de datos. Agregar a un arreglo dinámico es O(1) amortizado porque el raro redimensionamiento O(n) se compensa con las n operaciones baratas previas. Consulta las lecciones de arreglos y montículos para ver las demostraciones.

Cómo leer el gráfico

Cada barra es una operación clásica ejecutándose sobre el mismo arreglo de entrada de longitud N:

Clases

O(1) lookup arr[42] — una operación de CPU, sin importar N

O(log n) binary search — reduce a la mitad el espacio de búsqueda en cada paso

O(n) find max — toca cada elemento una vez

O(n log n) merge sort — n elementos, cada uno barajado a través de log n niveles de mezcla

O(n²) find all pairs — cada combinación (i,j)

Qué significan las dos barras

predicho el valor de la fórmula en este N (la asíntota)

real el conteo real de operaciones al ejecutar el algoritmo sobre un arreglo real

Las barras usan una escala logarítmica en el eje x. Esa es la única forma de que O(1) = 1 operación y O(n²) = 8 millones de operaciones quepan en el mismo gráfico. Calcular distancias a ojo es engañoso en un eje logarítmico — lee los números.

La trampa de la N pequeña

En N = 4 las barras son visualmente indistinguibles. O(1) = 1, O(n²) = 6. Seis es "básicamente nada". Por esto los ingenieros novatos escriben código O(n²) que funciona en las pruebas y colapsa en producción — el conjunto de prueba tenía 10 filas, la tabla de producción tiene 10 millones.

Para N = 1024:

Lo que cuestan 1024 elementos

O(1) 1 operación

O(log n) ~10 operaciones

O(n) 1,024 operaciones

O(n log n) ~10,240 operaciones

O(n²) 523,776 operaciones

Mismo algoritmo, misma máquina — los separan cinco órdenes de magnitud.

Profundizando

Algunas reglas prácticas en las que te apoyarás durante el resto del plan de estudios:

• Si ves un solo bucle sobre la entrada, tienes al menos O(n).
• Si ves bucles anidados que ambos recorren la entrada, estás en O(n²).
• Si el trabajo se reduce a la mitad en cada paso (recursión, búsqueda binaria, descenso por un árbol balanceado), es O(log n).
• Ordenar datos basándose en comparaciones es O(n log n) — no puedes superarlo en el caso general (cota inferior de teoría de la información).
• El hashing colapsa el bucle a O(1) esperado — a costa de renunciar al orden y a las garantías del peor caso.

Ahora — pasemos a las estructuras de datos en sí.