La notación Big-O expresa una cota superior asintótica: indica que el costo de un algoritmo no crece más rápido que cierta función, salvo por factores constantes y para entradas suficientemente grandes.
Big-O es una herramienta para describir crecimiento, no una unidad de tiempo. Decir que un algoritmo es O(n²) no significa que tarde n² segundos ni que haga exactamente n² operaciones. Significa que su costo puede acotarse superiormente por una constante multiplicada por n² a partir de cierto tamaño de entrada.
Esta abstracción permite comparar algoritmos aunque se ejecuten en computadoras distintas, estén escritos en lenguajes diferentes o tengan constantes internas diferentes.
La función g(n) es una cota superior. La constante c absorbe diferencias de implementación y n0 permite ignorar el comportamiento de entradas pequeñas, donde los términos de menor orden pueden ser relevantes.
Para demostrar que f(n) = 3n + 10 es O(n), debemos encontrar c y n0 que satisfagan 3n + 10 ≤ cn para n grande.
No necesitamos encontrar las mejores constantes. Basta con exhibir algunas que hagan verdadera la desigualdad.
Demostremos que f(n) = 3n² + 7n + 12 es O(n²).
El argumento ilustra una regla general: un polinomio de grado k con coeficientes positivos es O(nk).
La expresión «T(n) = O(n)» se usa habitualmente, pero no debe interpretarse como una igualdad numérica. O(n) representa un conjunto de funciones que no crecen más rápido que una función lineal, salvo constantes.
Cuando queremos describir un orden ajustado usaremos Θ (Theta), que estudiaremos más adelante.
| Expresión | Cota Big-O | Razón |
|---|---|---|
| 7 | O(1) | No depende de n. |
| 5n + 3 | O(n) | Domina el término lineal. |
| n² + 100n | O(n²) | Domina n². |
| n log n + n | O(n log n) | n log n domina n para n grande. |
| 2n + n10 | O(2n) | La exponencial domina al polinomio. |
Eliminar constantes y términos menores es válido solo en análisis asintótico. No debemos hacerlo si necesitamos una estimación exacta de tiempo, memoria o dinero.
Si un algoritmo ejecuta dos bloques consecutivos de costos T1(n) y T2(n), el costo total es la suma. Asintóticamente domina el bloque de mayor crecimiento.
La regla no dice que el primer bloque no se ejecute, sino que su contribución se vuelve pequeña en comparación con n² cuando n crece.
function maximo(numeros) {
if (numeros.length === 0) return undefined;
let mayor = numeros[0];
for (let i = 1; i < numeros.length; i++) {
if (numeros[i] > mayor) mayor = numeros[i];
}
return mayor;
}
console.log(maximo([8, 3, 12, 5, 9])); // 12El bucle ejecuta a lo sumo n - 1 comparaciones. Existe una constante c tal que el costo total es menor o igual que cn para n suficientemente grande; por lo tanto, el algoritmo es O(n).
Dos bucles independientes que recorren n elementos cada uno ejecutan el cuerpo interno n² veces. Si el cuerpo tiene costo constante, el algoritmo es O(n²).
function hayDuplicados(numeros) {
for (let i = 0; i < numeros.length; i++) {
for (let j = i + 1; j < numeros.length; j++) {
if (numeros[i] === numeros[j]) return true;
}
}
return false;
}
console.log(hayDuplicados([4, 8, 15, 16, 8])); // true
console.log(hayDuplicados([4, 8, 15, 16])); // falseEn el peor caso, cuando no hay duplicados, se comparan todos los pares posibles. La cantidad exacta es n(n - 1)/2, que pertenece a O(n²).
Un algoritmo que elimina aproximadamente la mitad de los candidatos en cada paso es O(log n). La búsqueda binaria es el ejemplo clásico.
La eficiencia logarítmica depende de que cada paso descarte una fracción constante de la entrada y no solo unos pocos elementos.
Para algoritmos recursivos, primero planteamos una recurrencia y después obtenemos una cota. Merge sort cumple aproximadamente T(n) = 2T(n/2) + cn, cuyo resultado es O(n log n).
La cota incluye todas las llamadas y el trabajo de combinación. Analizar solo una llamada recursiva daría una estimación incorrecta.
En muchos cursos se informa Big-O como cota de peor caso, pero la notación por sí misma no significa «peor caso». Debemos indicar qué función estamos acotando: tiempo máximo, mínimo, esperado o espacio usado.
La notación Big-O también describe espacio. Un algoritmo que crea una copia de un arreglo de n elementos usa O(n) memoria adicional; una matriz n × n usa O(n²).
| Recurso | Ejemplo | Cota |
|---|---|---|
| Memoria constante | Recorrer un arreglo con un acumulador. | O(1) |
| Memoria lineal | Guardar una copia del arreglo. | O(n) |
| Pila recursiva | Factorial recursivo. | O(n) |
| Matriz | Tabla de distancias entre n nodos. | O(n²) |
Si un algoritmo es O(n), también es O(n²), O(n³) y O(2n), porque esas funciones crecen más rápido. Sin embargo, dar una cota demasiado grande pierde información importante.
La notación Theta permitirá expresar formalmente que una función está acotada por arriba y por abajo por el mismo orden.
| Regla | Ejemplo |
|---|---|
| Constante por función | O(cg(n)) = O(g(n)). |
| Suma | O(f(n) + g(n)) = O(max(f(n), g(n))). |
| Producto | O(f(n)) · O(g(n)) = O(f(n)g(n)). |
| Transitividad | Si f ∈ O(g) y g ∈ O(h), entonces f ∈ O(h). |
Estas reglas ayudan a combinar costos, pero debemos aplicarlas a expresiones válidas. Por ejemplo, el costo de una rama condicional no siempre es la suma de ambas ramas: en peor caso se toma la más costosa que pueda ejecutarse.
Supongamos un algoritmo que primero ordena un arreglo y después lo recorre una vez. Si usamos un ordenamiento O(n log n), el costo total es:
La fase lineal sigue siendo necesaria, pero no modifica el orden total. Esta forma de razonamiento ayuda a estimar pipelines de procesamiento compuestos por varias etapas.
Medir tiempos reales complementa Big-O. Las mediciones revelan constantes, efectos de caché, asignación de memoria, optimizaciones del lenguaje y distribuciones de entrada. Big-O explica la tendencia que esperamos al crecer n.
function operacionesLineales(n) {
let contador = 0;
for (let i = 0; i < n; i++) contador++;
return contador;
}
console.log(operacionesLineales(10)); // 10
console.log(operacionesLineales(100)); // 100Duplicar n duplica las operaciones principales de este ejemplo. Una medición de tiempo puede variar, pero el conteo revela el crecimiento lineal.
Big-O permite garantizar que un costo no crecerá más rápido que cierto orden. En el próximo tema estudiaremos Ω (Omega), la notación que expresa cotas inferiores asintóticas.