Última actualización: 2026-06-23

Crecimiento Big-O

La notación Big-O clasifica cómo escala la demanda de recursos de un algoritmo con el tamaño de la entrada. En lugar de medir segundos en una máquina concreta, captura la forma del crecimiento: ¿se duplica el trabajo cuando n se duplica, o se cuadruplica? Las seis complejidades siguientes son las que se encuentran con mayor frecuencia en libros de texto y entrevistas técnicas.

Las seis clases habituales

O(log n) — Logarítmica. Cada paso elimina una fracción constante del trabajo restante. Una búsqueda binaria sobre un vector ordenado de mil millones de elementos requiere solo 30 comparaciones, porque en cada paso reduce a la mitad el espacio de búsqueda. Las consultas en árboles de búsqueda binaria equilibrados y muchas recurrencias de divide y vencerás caen en esta categoría.

O(n) — Lineal. El trabajo crece en proporción directa al tamaño de la entrada. Recorrer un vector una vez para encontrar su máximo, contar los caracteres de una cadena o leer todos los elementos de una lista son operaciones lineales. Los algoritmos lineales se consideran en general eficientes.

O(n log n) — Lineal-logarítmica. La complejidad más habitual para la ordenación. Merge sort, heapsort y Timsort (utilizado en Python y Java) alcanzan todos O(n log n), que es también el límite teórico inferior para la ordenación basada en comparaciones. Con $n = 10^6$, esto equivale a unos veinte millones de operaciones: rápido en la práctica.

O(n²) — Cuadrática. Dos bucles anidados sobre la entrada. Bubble sort, insertion sort y la multiplicación matricial ingenua tienen un coste de O(n²) en el peor caso. Con $n = 10^4$, son cien millones de operaciones; con $n = 10^6$ se convierte en un billón, impracticable para datos grandes.

O(2ⁿ) — Exponencial. El trabajo se duplica con cada elemento adicional. El algoritmo recursivo ingenuo de Fibonacci recalcula subproblemas de forma exponencial; la enumeración por fuerza bruta de todos los subconjuntos de un conjunto también crece como $2^n$. Con n = 40, el recuento supera un billón.

O(n!) — Factorial. La clase de crecimiento más rápido en el análisis algorítmico cotidiano. Las soluciones por fuerza bruta a problemas de permutaciones —como enumerar todos los posibles recorridos en el Problema del Viajante— realizan una operación por permutación, y hay $n!$ permutaciones en total. Con n igual a veinte, el recuento supera los dos trillones de operaciones (en escala larga: $2 \times 10^{18}$).

Ejemplo resuelto con n = 20

$\log_2 20 \approx 4{,}32 \quad\quad 20 \quad\quad 20 \log_2 20 \approx 86{,}4$

$20^2 = 400 \quad\quad 2^{20} = 1\,048\,576 \quad\quad 20! \approx 2{,}43 \times 10^{18}$

La razón entre O(n log n) y O(n!) con n = 20 es de aproximadamente $10^{16}$: la diferencia entre una ordenación rápida y esperar más tiempo del que lleva el universo en existir.

Orientaciones prácticas

Los factores constantes y los efectos de caché importan para n pequeño; la complejidad domina para n grande. Un umbral aproximado de n = 10.000 es donde O(n²) empieza a ser incómodo en hardware moderno (suponiendo operaciones simples). A partir de $n = 10^6$, en general se necesita un algoritmo de O(n log n) o mejor. Los algoritmos exponenciales y factoriales requieren aproximaciones, programación dinámica o estrategias de poda para cualquier entrada real.

Conversor de Base Numérica resulta útil cuando se trabaja con representaciones binarias del espacio de entrada.