Cómo Crecen los Costos

Big O mide cómo crecen los costos a medida que el input crece. No el factor constante - la tasa. Dos algoritmos que ambos funcionan en 'unos pocos milisegundos' en N=100 pueden divergir en un factor de 10,000 en N=10,000, si uno funciona en O(N) de tiempo y el otro en O(N²).

Las Clases de Complejidad Más Comunes

O(1) — Constante. El costo es el mismo sin importar N. Ejemplos: consulta de tabla de hash por clave, acceso a matriz por índice, empujar y extraer de pila. Duplicar N no cambia nada.

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

O(N) — Lineal. El costo crece con la entrada. Ejemplos: escaneo lineal de una lista, leer un archivo, contar elementos en una colección. A N=10,000: 10,000 operaciones.

O(N log N) — Linealítmico. Casi lineal, ligeramente peor. Ejemplos: ordenamiento por mezcla, algoritmos de caminos más eficientes (Dijkstra con una pila). A N=10,000: ~133,000 operaciones.

O(N²) — Cuadrática. El costo explota. Ejemplos: list.contains() llamado dentro de un bucle en la misma lista, ordenamiento por burbujas, comparación de pares naif. A N=1,000: 1,000,000 operaciones. A N=10,000: 100,000,000 operaciones.

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

La escala en la que se vuelve visible

N=10 comparaciones:
  O(N):   10
  O(N²):  100
  relación:  10x

N=1.000 comparaciones:
  O(N):   1.000
  O(N²):  1.000.000
  relación:  1.000x

N=10.000 comparaciones:
  O(N):   10.000
  O(N²):  100.000.000
  relación:  10.000x

A N=10, la diferencia apenas se nota. A N=10.000, el algoritmo O(N²) tarda 10.000 veces más. Por eso MOAD-0001 permaneció invisible durante décadas: los gráficos en los que corría en 1993 tenían 50 nodos. En 2020, el mismo código corría en gráficos de dependencia con 50.000 nodos.

Clasificar Tres Operaciones

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

Código Correcto, Curva de Crecimiento Errónea

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

Esta propiedad hace que los defectos de O(N²) sean sedimentarios: se calcifican dentro del código en funcionamiento 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 extendida: visited = [] dentro de un bucle de recorrido de gráficos.

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

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

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

El mismo comportamiento. El mismo resultado. Las mismas pruebas que pasan. El ritmo de crecimiento cambia de O(N²) a O(N). A N=1,000: 1,000 veces más rápido. A N=10,000: 10,000 veces más rápido.

Por qué la era de Hamming sembró esto

En Java y C tempranos, ArrayList (arreglo dinámico) era el contenedor secuencial predeterminado. Los conjuntos existían, pero no eran idiomáticos. Los desarrolladores llegaban a lo que era familiar. En 1993, un recorrido de gráficos con N=50 corría en microsegundos con visited = []. Ese código entró en control de versiones, se copió, se envolvió en bibliotecas y se distribuyó en administradores de paquetes. En 2020, el mismo patrón corría en gráficos de dependencias con 50,000 nodos.

El código era correcto en 1993. Se volvió caro cuando el mundo que lo rodeaba cambió. La era de Hamming sembró esta clase de defectos al no nombrar la pregunta sobre el ritmo de crecimiento.

Diagnóstico y solución

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

¿Cambios en los nombres

Antes de que Big O tuviera un nombre, los programadores notaron 'esto corre lento'. Profilaron. Escribieron de nuevo. Pero no podían enseñar el patrón - solo podían señalar a instancias. Un patrón sin un nombre no puede propagarse.

Después de que Big O tuvo un nombre, un ingeniero senior podía decir 'esto es O(N²), reemplázalo con un conjunto' y un ingeniero junior podía entender, aplicar y enseñar el patrón a su vez. El nombre hizo que el patrón fuera una unidad de conocimiento transferible.

Hamming conoció este dinámica en otros dominios. Describió cómo nombrar 'código espagueti' en la década de 1960 permitió a la comunidad reconocer, discutir y eventualmente 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 agrega 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, predice el rendimiento a gran escala y comunica las soluciones con precisión. Cumplen con el propio test de Hamming para una fundamentación: duradero y generativo de la mayor parte del resto del campo.

De la teoría de números a la Ciencia de la Computación

La notación O de Big O no surgió 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 los algoritmos.

Paul Bachmann, 1894

Paul Bachmann, un matemático alemán, introdujo la notación O en su libro de 1894 Die Analytische Zahlentheorie (Teoría Numérica Analítica). Necesitaba una manera compacta de expresar que una cantidad crece al más lento que otra, hasta un factor constante. Escribir 'f(n) = O(g(n))' decía: f crece al más lento que g. Esto le permitió a los teóricos de los números racionales razonar sobre términos de error en aproximaciones sin seguir exactamente las constantes.

Bachmann no estaba pensando en bucles, estructuras de datos o tiempo de ejecución. Estaba pensando en cómo se distribuyen los números primos - específicamente sobre los términos de error en el 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 de la Teoría de la Distribución de los Números Primos) de 1909. Landau también introdujo las notaciones relacionadas o (pequeño-o) y utilizó ampliamente la familia de símbolos asintóticos, por lo que la familia se conoce como notación de Bachmann-Landau o simplemente notación de Landau.

Durante seis décadas, la notación O vivió enteramente en las matemáticas. Ningún programador pensó en ella.

Donald Knuth, 1968 & 1976

Donald Knuth tradujo la notación al ámbito de la informática. 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, un trasplante directo de la herramienta de Bachmann a un nuevo dominio. Fue el primero en aplicarla de manera sistemática 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 la Omega (Omega) para límites inferiores y la Theta para límites estrechos, completando la vocabulario de tres símbolos que hoy en día se utiliza en la informática. También argumentó a favor de la estandarización del uso de estos símbolos en 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. A finales de la década de 1990, se había convertido en el vocabulario estándar de las entrevistas.

Un viaje de 74 años

1894 — Bachmann introduce O en la teoría de números
1909 — Landau populariza O, o y la familia completa 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; argumenta a favor de la estandarización
1980s — Big O entra en todos los currículos de CS
1993 — MOAD-0001 capa de sedimentos se forma en el código en producción
1995 — Hamming enseña la última versión de su curso; nunca cubre Big O
2026 — MOAD-0001 encontrado en 1,000+ proyectos de código abierto

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

Por qué la estandarización de Knuth importó

El artículo de Knuth de 1976 hizo algo más allá de introducir la Omega y la Theta. Argumentó que el campo necesitaba una notación consistente y que una notación inconsistente era dañina de manera activa. Diferentes libros de texto utilizaban O para significar cosas diferentes — a veces como un límite superior, a veces como una aproximación, a veces sin especificar si importaban las constantes. Knuth limpió esto.

Este es el patrón dinámico de nombrado de Hamming aplicado a la notación en sí. Antes de que Knuth estandarizara los símbolos, los ingenieros no podían comunicar precisamente las reclamaciones de complejidad entre libros de texto, artículos o equipos. Después de la estandarización, 'esto funciona en O(N log N)' tenía un único significado independientemente de quién lo dijera.

Knuth también contribuyó con la traducción informal: 'O(f(n)) significa que el tiempo de ejecución es en absoluto un factor constante f(n), para todos los n lo suficientemente grandes'. Esta interpretación -límite superior, hasta un factor constante, para entradas grandes- se convirtió en la intuición estándar que cada programador aprende.