Explorador de complejidad Big-O

Observa cómo crecen las clases de complejidad de los algoritmos a medida que aumenta el tamaño de entrada N.

Ejemplo resuelto — Explorador de complejidad Big-O

O(1)	1
O(log N)	7
O(N)	100
O(N log N)	664
O(N²)	10.000

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — Explorador de complejidad Big-O

La notación O grande es una cota superior del crecimiento, no una medida de tiempo. Decir que un algoritmo es O(N²) afirma que, a partir de cierto tamaño de entrada, su trabajo se mantiene por debajo de un múltiplo fijo de N² — no dice nada sobre segundos ni tampoco sobre entradas pequeñas.

Qué significa cada símbolo

N: el tamaño de la entrada — cuántos elementos recibe el algoritmo. Es el número establecido arriba, de 2 a 1.000.000.
f(N): el trabajo realmente realizado con ese tamaño, contado en operaciones abstractas en lugar de segundos.
c: un multiplicador constante que la notación tiene permitido ocultar. La afirmación es f(N) ≤ c·g(N); c podría ser 2 o 2000, y esa es precisamente la información que la notación O grande descarta.
n₀: el tamaño a partir del cual debe cumplirse la cota. Por debajo de n₀ las clases pueden ordenarse de cualquier manera, razón por la cual los cinco números anteriores se agrupan cuando N es pequeña.

De dónde viene la fórmula

Comienza a partir de la afirmación que se debe precisar: el trabajo f(N), a la larga, no crece más rápido que alguna función de referencia g(N).
“No más rápido” debe tolerar un factor constante, porque optimizar un bucle interno cambia la constante y no la forma. Así que se permite un multiplicador: f(N) ≤ c·g(N).
Y “a la larga” debe disculpar las entradas pequeñas, donde puede pasar cualquier cosa. Exige la desigualdad solo cuando N ≥ n₀. En conjunto: f(N) = O(g(N)) significa que existen algún c > 0 y algún n₀ tales que f(N) ≤ c·g(N) para todo N ≥ n₀.

Cómo leer lo que ves

Las cinco filas representan un mismo tamaño de entrada evaluado en cinco clases de crecimiento con todas las constantes fijadas en 1 — de modo que son conteos de operaciones, no tiempos de ejecución. Con el valor predeterminado N = 100, muestran 1, 7, 100, 664 y 10,000. El logaritmo es en base 2: log₂ 100 ≈ 6.64, razón por la cual O(log N) muestra 7 y O(N log N) muestra 664 en lugar de 700.

Supone: Que una operación cuesta lo mismo que cualquier otra y que el conteo es exacto en lugar de medido. Eso es lo que hace que la comparación sea limpia e igualmente lo que la hace abstracta — los patrones de acceso a memoria, el comportamiento de la caché y el disco quedan fuera de este modelo, y en el hardware real deciden habitualmente cuál de dos algoritmos gana.
Falla cuando: La cota no promete nada por debajo de n₀, y puedes verlo directamente: establece N = 2 y las cinco clases muestran 1, 1, 2, 2 y 4 — prácticamente indistinguibles. El orden que la notación garantiza solo emerge cuando N es grande, razón por la cual un método O(N²) con una constante pequeña puede superar a uno O(N log N) en cualquier entrada que llegues a tener en la práctica.

Cuando el crecimiento supera cualquier optimización 🖖

Big-O describe cómo crece el trabajo a medida que aumenta el tamaño de la entrada. Un único bucle crece aproximadamente con N, los bucles anidados suelen crecer con N², y la recursión ramificada puede crecer exponencialmente. La lección importante es la escala: con N pequeño, muchos enfoques se ven similares, pero con N grande la clase de crecimiento domina el tiempo de ejecución.

La prueba de duplicar 🖖

La forma más clara de percibir una clase de crecimiento es duplicar la entrada y observar qué le ocurre al trabajo. Con O(log N) apenas se mueve — la búsqueda binaria encuentra un elemento entre un millón en unas 20 comparaciones. Con O(N) el trabajo se duplica, y con O(N²) se cuadruplica. Desliza N en esta herramienta y verás cómo las distancias pasan de invisibles a abrumadoras.

Cuando la clase más rápida pierde 🖖

Una clase de crecimiento menor no garantiza un programa más rápido. Los informáticos llaman a las excepciones algoritmos galácticos: métodos con mejor notación Big-O cuyo factor constante oculto es tan enorme que solo superan a los métodos sencillos con entradas mayores que cualquier cosa del universo físico. Varios algoritmos récord de multiplicación de matrices nunca se usan en la práctica justo por esto: Big-O descarta en silencio las constantes que deciden la velocidad real.

Problema resuelto al detalle

Dónde se abre la brecha entre N log N y N ² 5 pasos
Con N = 100, el panel muestra 664 para N log N y 10 000 para N². Eso es solo un factor de quince, distando mucho del abismo que se presupone entre clases de complejidad. Averigüe dónde se abre realmente el abismo.
1. Comience por los dos números. log₂ 100 es 6,6439, de modo que N log₂ N es 664 y N² es 10 000.
  
  $N lo g_{2} N = 100 \times 6.6439 = 664, N^{2} = 10000$
2. La razón entre ellos no es constante, y esa es la clave de las clases de complejidad. Al dividir, N se simplifica una vez, dejando N/log N —una cantidad que crece sin límite, solo que despacio.
3. Con N = 100 es 15,1. Es una diferencia real pero poco impresionante: una aceleración de quince veces es la clase de mejora que un mejor factor constante podría proporcionar, que es exactamente la razón por la que las pruebas de rendimiento con entradas pequeñas inducen a error.
  
  $\frac{N ^{2}}{N lo g _{2} N} = \frac{N}{lo g _{2} N} = \frac{100}{6.6439} = 15.1$
4. Introduzca ahora un millón. El logaritmo apenas se ha movido —de 6,6 a 19,9, un factor de tres— mientras que N ha aumentado diez mil veces. La razón es ahora de 50 172.
  
  $N = 1 0^{6} : \frac{N}{lo g _{2} N} = \frac{1 0 ^{6}}{19.93} = 50172$
5. Y nunca invierte la tendencia. La derivada de N/log N es positiva para todo N superior a e, de modo que no existe un tamaño de entrada a partir del cual el algoritmo cuadrático lo alcance.
  
  $\frac{d}{d N} (\frac{N}{lo g _{2} N}) > 0 for N > e ⟹ the gap only widens$
Respuesta

La herramienta muestra 664 frente a 10 000 para N = 100. La cifra que conviene recordar es la otra: para un millón, esas mismas dos curvas están separadas por 50 172. Las clases de complejidad no se refieren a un centenar de elementos, y compararlas ahí es la forma habitual de convencerse a uno mismo de elegir el algoritmo equivocado —una diferencia de quince veces parece algo que un lenguaje más rápido podría recortar—. Mueva el deslizador hacia arriba y observe cómo la razón aumenta con él. Esa es también la razón por la que el logaritmo se ignora tan a menudo en la práctica: creció por un factor de tres mientras que la entrada se multiplicó por diez mil.

$\frac{N ^{2}}{N lo g N} = \frac{N}{lo g N} : 15 \times at 100, 50172 \times at 1 0^{6}$

Ruta de aprendizaje

Contar trabajo, no segundos

Lleva a sorting-race

Referencias (1)

The definition the lesson states, and the case for using it carefully: D. E. Knuth, “Big Omicron and big Omega and big Theta.” ACM SIGACT News 8, 18–24, 1976.

Por el equipo de 42Math · Actualizado 2026-06-10

Contrastado con fuentes publicadas. Se agradecen correcciones. Política editorial · Correcciones

Todas las lecciones de Informática →

Problemas de ejemplo

N pequeño = 20 - Todas las curvas en N=20
N=1000 - N=1000: las curvas polinómicas divergen
Escala log - La escala logarítmica revela las diferencias de crecimiento
Constantes ocultas - Con c=50, 50N log N y N² se cruzan cerca de N=439