Cómo Crece el Costo

Big O mide cómo crece el costo a medida que crece la entrada. No el factor constante — la tasa. Dos algoritmos que ambos se ejecutan en 'unos pocos milisegundos' con N=100 pueden divergir por un factor de 10,000 con N=10,000, si uno se ejecuta en tiempo O(N) y el otro en O(N²).

Las Clases de Complejidad Comunes

O(1) — Constante. Mismo costo independientemente de N. Ejemplos: búsqueda en tabla hash por clave, acceso a arreglo por índice, push/pop en pila. Duplicar N no cambia nada.

O(log N) — Logarítmico. Cada paso reduce a la mitad el trabajo restante. Ejemplos: búsqueda binaria en un arreglo ordenado, consulta espacial BVH en un motor de juegos, operaciones en árboles binarios balanceados. En N=1,000,000: log₂(1,000,000) ≈ 20 pasos.

O(N) — Lineal. El costo crece con la entrada. Ejemplos: recorrido lineal de una lista, lectura de un archivo, conteo de elementos en una colección. En N=10,000: 10,000 operaciones.

O(N log N) — Lineal-logarítmico. Casi lineal, ligeramente peor. Ejemplos: ordenamiento por mezcla (merge sort), algoritmos eficientes de camino más corto (Dijkstra con heap). En N=10,000: ~133,000 operaciones.

O(N²) — Cuadrático. El costo explota. Ejemplos: list.contains() llamado dentro de un bucle sobre la misma lista, ordenamiento burbuja, comparación ingenua de todos los pares. En N=1,000: 1,000,000 operaciones. En N=10,000: 100,000,000 operaciones.

O(2^N) — Exponencial. Inutilizable a cualquier escala significativa. Ejemplos: combinatoria por fuerza bruta, encontrar todos los subconjuntos. En N=30: más de 1.000.000.000 operaciones.

La escala que lo hace visible

Comparaciones N=10:
O(N):   10
O(N²):  100
ratio:  10x

N=1.000 comparaciones:
O(N):   1.000
O(N²):  1.000.000
ratio:  1.000x

N=10.000 comparaciones:
O(N):   10,000
O(N²):  100,000,000
ratio:  10,000x

En N=10, la diferencia apenas se nota. En N=10,000, el algoritmo O(N²) se ejecuta 10,000 veces más lento. Por eso MOAD-0001 pasó desapercibido durante décadas: los grafos en los que se ejecutaba en 1993 tenían 50 nodos. Para 2020, el mismo código se ejecutaba en grafos de dependencias con 50,000 nodos.

Clasificar Tres Operaciones

Aplica las clases de complejidad a operaciones concretas. La pregunta clave para cada una: ¿cuántas operaciones toma a medida que crece N?

Código Correcto, Curva de Crecimiento Incorrecta

El código correcto que se ejecuta en tiempo O(N²) produce resultados idénticos al código O(N). Las pruebas pasan. La salida coincide. Ninguna excepción se dispara. El defecto se oculta en la curva de crecimiento.

Esta propiedad hace que los defectos O(N²) sean sedimentarios: se calcifican dentro de código que funciona y solo se vuelven visibles cuando N crece más allá de un umbral. El código no cambió. El mundo que lo rodea cambió.

MOAD-0001: El Defecto Sedimentario

La instancia más común: visited = [] dentro de un bucle de recorrido de grafos.

visited = []
for node in graph:
if node not in visited:  # escaneo O(N) en cada llamada
visited.append(node)
process(node)

Cada llamada a not in visited recorre de 0 a len(visited)-1 elementos. N llamadas × N/2 elementos promedio = O(N²) en total. La solución: una sola línea.

visited = set()  # prueba de pertenencia O(1)
for node in graph:
if node not in visited:  # búsqueda hash O(1)
visited.add(node)
process(node)

Mismo comportamiento. Misma salida. Mismos tests pasando. La tasa de crecimiento cambia de O(N²) a O(N). En N=1,000: 1,000× más rápido. En N=10,000: 10,000× más rápido.

¿Por qué la era de Hamming sembró esto?

En los primeros Java y C, ArrayList (arreglo dinámico) era el contenedor secuencial predeterminado. Los conjuntos existían, pero no eran idiomáticos: los desarrolladores usaban lo que les resultaba familiar. Un recorrido de grafo en 1993 con N=50 se ejecutaba en microsegundos con visited = []. Ese código entró en el control de versiones, se copió, se envolvió en bibliotecas y se distribuyó en gestores de paquetes. Para 2020, el mismo patrón se ejecutaba en grafos de dependencias con 50,000 nodos.

El código era correcto en 1993. Se volvió costoso cuando el mundo a su alrededor cambió. La era de Hamming sembró esta clase de defecto al no nombrar nunca la pregunta sobre la tasa de crecimiento.

Diagnosticar y corregir

Aplica el diagnóstico: encuentra el patrón O(N²) e identifica la corrección.

¿Qué cambios de nomenclatura

Antes de que Big O tuviera un nombre, los programadores notaban que «esto se ejecuta lento». Perfilaban. Reescribían. Pero no podían enseñar el patrón — solo podían señalar instancias. Un patrón sin nombre no puede propagarse.

Una vez que Big O tuvo un nombre, un ingeniero senior podía decir «esto es O(N²), reemplázalo por un conjunto» y un ingeniero junior podía entenderlo, aplicarlo y enseñar el patrón a su vez. El nombre convirtió el patrón en una unidad de conocimiento transferible.

Hamming conocía esta dinámica en otros dominios. Describió cómo nombrar «código espagueti» en los años 60 permitió a la comunidad reconocer, discutir y finalmente erradicar una clase de defecto que todos habían experimentado pero nadie había nombrado. El mismo mecanismo se aplica a las clases de complejidad.

Unhamming añade el vocabulario que Hamming omitió: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). Estos nombres te permiten ver la curva de crecimiento en el código que lees, predecir el rendimiento a escala y comunicar correcciones con precisión. Cumplen la propia prueba de Hamming para un concepto fundamental: duradero y generador de la mayor parte del resto del campo. [TITLE who_coined_big_o/]

De la Teoría de Números a la Ciencia de la Computación

La notación Big O no se originó en la ciencia de la computación. Surgió en las matemáticas puras —específicamente en la teoría de números— 74 años antes de que Donald Knuth la adaptara para algoritmos.

Paul Bachmann, 1894

Paul Bachmann, matemático alemán, introdujo la notación O en su libro de 1894 Die Analytische Zahlentheorie (Teoría Analítica de Números). Necesitaba una forma compacta de expresar que una cantidad no crece más rápido que otra, hasta un factor constante. Escribir 'f(n) = O(g(n))' significaba: f crece como máximo tan rápido como g. Esto permitió a los teóricos de números razonar sobre términos de error en aproximaciones sin tener que seguir constantes exactas.

Bachmann no pensaba en bucles, estructuras de datos ni tiempo de ejecución. Pensaba en cómo se distribuyen los números primos —específicamente en los términos de error del Teorema de los Números Primos.

Edmund Landau, 1909

Edmund Landau, otro matemático alemán, popularizó la notación en su Handbuch der Lehre von der Verteilung der Primzahlen (Manual sobre la Distribución de los Números Primos) de 1909. Landau también introdujo la notación relacionada o (pequeña-o) y utilizó la familia de símbolos asintóticos de forma tan extensa que la familia pasó a conocerse como notación de Bachmann-Landau o simplemente notación de Landau.

Durante seis décadas, la notación O vivió exclusivamente en el ámbito de las matemáticas. Ningún programador pensaba en ella.

Donald Knuth, 1968 & 1976

Donald Knuth tradujo la notación al campo de la ciencia de la computación. En The Art of Computer Programming (Vol. 1, 1968), Knuth utilizó la notación O para describir el tiempo de ejecución de los algoritmos —una transferencia directa de la herramienta de Bachmann a un nuevo dominio. Fue el primero en aplicarla sistemáticamente al análisis de algoritmos.

En 1976, Knuth publicó un breve artículo en SIGACT News titulado 'Big Omicron and Big Omega and Big Theta.' Introdujo Omega (Ω) para los límites inferiores y Theta (Θ) para los límites ajustados, completando el vocabulario de tres símbolos que la ciencia de la computación utiliza hoy en día. También abogó por estandarizar el uso de estos símbolos en todo el campo —un acto de estandarización deliberada que aceleró su adopción.

A principios de la década de 1980, Big O aparecía en todos los libros de texto de algoritmos. En la década de 1990, ya era vocabulario estándar en entrevistas.

Un viaje de 74 años

1894 — Bachmann introduce O en la teoría de números
1909 — Landau populariza O, o y toda la familia de notaciones
1953 — Hamming comienza su investigación en Bell Labs (nunca aprende Big O como herramienta de CS)
1968 — Knuth aplica O al análisis de algoritmos en TAOCP Vol. 1
1976 — Knuth añade Omega y Theta; defiende la estandarización
1980s — Big O se incorpora a todos los planes de estudio de CS
1993 — La capa de sedimento MOAD-0001 se forma en el código de producción
1995 — Hamming imparte la última versión de su curso; nunca cubre Big O
2026 — MOAD-0001 se encuentra en más de 1 000 proyectos de código abierto

La herramienta de Bachmann pasó 74 años en matemáticas puras, visible para todo matemático pero invisible para todo programador. Knuth vio el trasplante. Hamming —trabajando en la misma época, colaborando con la misma comunidad de computación— nunca lo incluyó en su curso.

Por qué la estandarización de Knuth importó

El artículo de Knuth de 1976 hizo algo más que introducir Omega y Theta. Argumentó que el campo necesitaba una notación consistente, y que la notación inconsistente era activamente perjudicial. Diferentes libros de texto usaban O para significar cosas distintas —a veces como cota superior, a veces como aproximación, a veces sin especificar si las constantes importaban—. Knuth lo aclaró.

Este es el patrón de nombrar patrones de Hamming aplicado a la notación misma. Antes de que Knuth estandarizara los símbolos, los ingenieros no podían comunicar afirmaciones de complejidad con precisión entre libros de texto, artículos o equipos. Tras la estandarización, «esto se ejecuta en O(N log N)» tenía exactamente un significado, independientemente de quién lo dijera.

Knuth también aportó la traducción informal: «O(f(n)) significa que el tiempo de ejecución es como máximo una constante multiplicada por f(n), para todos los n suficientemente grandes». Esta interpretación —cota superior, hasta un factor constante, para entradas grandes— se convirtió en la intuición estándar que todo programador aprende.