La notación Θ expresa una cota asintótica ajustada: una función queda acotada simultáneamente por arriba y por abajo por el mismo orden de crecimiento.
Big-O indica que una función no crece más rápido que cierto orden; Ω indica que no crece más lento. Cuando ambas cotas coinciden en la misma función g(n), obtenemos una descripción más precisa: f(n) pertenece a Θ(g(n)).
En análisis de algoritmos, Θ suele ser la notación preferida cuando conocemos el orden real de crecimiento. Por ejemplo, la búsqueda lineal de peor caso no solo es O(n), también es Ω(n); por eso es Θ(n).
La función f queda «encerrada» entre dos múltiplos de g. No necesitamos que f y g tengan los mismos valores, sino que crezcan con la misma tasa salvo factores constantes.
| Notación | Tipo de cota | Pregunta |
|---|---|---|
| O(g(n)) | Superior | ¿No crece más rápido que g(n)? |
| Ω(g(n)) | Inferior | ¿Crece al menos como g(n)? |
| Θ(g(n)) | Superior e inferior | ¿Crece exactamente de ese orden? |
Demostremos que f(n) = 3n + 10 pertenece a Θ(n).
Para f(n) = 3n² + 7n + 12, ya sabemos que es O(n²) y Ω(n²). Podemos reunir ambas pruebas.
Los coeficientes 3 y 22 son solo una elección válida. No hace falta encontrar los límites más estrechos para demostrar el orden Theta.
Una función Θ(n) también pertenece a O(n²), pero O(n²) es una cota superior floja: no distingue un algoritmo lineal de uno cuadrático. Theta se usa para comunicar la información más precisa disponible.
| Función | Cota válida | Cota ajustada |
|---|---|---|
| 7n + 2 | O(n²) | Θ(n) |
| n² + n | O(n³) | Θ(n²) |
| log n | O(n) | Θ(log n) |
| 2n + 1 | O(3n) | Θ(2n) |
Las reglas de composición son parecidas a las de Big-O cuando trabajamos con funciones no negativas.
| Regla | Resultado |
|---|---|
| Constante por función | Θ(cg(n)) = Θ(g(n)), si c > 0. |
| Suma | Θ(f(n)) + Θ(g(n)) = Θ(max(f(n), g(n))). |
| Producto | Θ(f(n)) · Θ(g(n)) = Θ(f(n)g(n)). |
| Transitiva | Si f ∈ Θ(g) y g ∈ Θ(h), entonces f ∈ Θ(h). |
Las reglas resumen costos, pero debemos mirar el flujo del algoritmo. Dos ramas alternativas no se suman si solo una puede ejecutarse en cada llamada.
En el peor caso, búsqueda lineal compara el valor buscado con todos los n elementos. No puede hacer menos de n comparaciones en ese caso concreto y tampoco hace más de n.
Es importante decir «en peor caso». El mejor caso ocurre si el valor está al principio y su tiempo es Θ(1).
function buscarLineal(numeros, buscado) {
let comparaciones = 0;
for (let i = 0; i < numeros.length; i++) {
comparaciones++;
if (numeros[i] === buscado) return { indice: i, comparaciones };
}
return { indice: -1, comparaciones };
}
console.log(buscarLineal([2, 4, 6, 8, 10], 10)); // { indice: 4, comparaciones: 5 }
console.log(buscarLineal([2, 4, 6, 8, 10], 7)); // { indice: -1, comparaciones: 5 }En ambas entradas se recorren todos los elementos. La cantidad exacta puede expresarse como n; por eso la cota superior e inferior coinciden.
En búsqueda binaria, cada comparación descarta aproximadamente la mitad de los candidatos. El algoritmo necesita a lo sumo un número proporcional a log n de pasos y, para ciertos valores, necesita al menos esa cantidad.
Una cota Theta es más informativa que decir simplemente O(log n), porque indica que no podemos esperar que el peor caso sea constante.
Merge sort divide un arreglo en dos mitades y combina resultados recorriendo todos los elementos. Su recurrencia es T(n) = 2T(n/2) + cn.
La cota inferior surge porque cada nivel realiza trabajo lineal y hay una cantidad logarítmica de niveles; la cota superior usa el mismo conteo. Por eso el orden queda ajustado.
Si un algoritmo compara cada par de elementos de un arreglo, en el peor caso realiza n(n - 1)/2 comparaciones. Esa cantidad está acotada por arriba y abajo por múltiplos de n².
function compararTodosLosPares(numeros) {
let comparaciones = 0;
for (let i = 0; i < numeros.length; i++) {
for (let j = i + 1; j < numeros.length; j++) {
comparaciones++;
}
}
return comparaciones;
}
console.log(compararTodosLosPares([1, 2, 3, 4, 5])); // 10Para n ≥ 2, n(n - 1)/2 está entre n²/4 y n²/2. Por lo tanto, el conteo pertenece a Θ(n²).
Las recurrencias permiten demostrar cotas Theta cuando conocemos tanto el trabajo de los subproblemas como el trabajo local. El teorema maestro resuelve muchos casos de la forma T(n) = aT(n/b) + f(n).
| Recurrencia | Resultado |
|---|---|
| T(n) = T(n - 1) + c | Θ(n) |
| T(n) = T(n/2) + c | Θ(log n) |
| T(n) = 2T(n/2) + cn | Θ(n log n) |
| T(n) = 4T(n/2) + c | Θ(n²) |
Un algoritmo puede tener una complejidad temporal y espacial diferente. Por ejemplo, factorial iterativo es Θ(n) en tiempo y Θ(1) en espacio auxiliar; factorial recursivo es Θ(n) en tiempo y Θ(n) en pila de llamadas.
function factorialIterativo(n) {
let resultado = 1;
for (let i = 2; i <= n; i++) {
resultado *= i;
}
return resultado;
}
console.log(factorialIterativo(5)); // 120La elección de una implementación debe considerar ambos recursos y también la claridad del código.
Una misma función puede tener Theta distintos según el caso que midamos. En inserción ordenada, por ejemplo, el mejor caso puede ser Θ(n) y el peor caso Θ(n²). Ninguno contradice al otro porque describen funciones de costo diferentes.
Dos algoritmos Θ(n) pueden tener rendimientos muy distintos para tamaños concretos. Las constantes, la memoria, la caché, el lenguaje, el compilador y los datos influyen en el tiempo real.
function contarHasta(n) {
let contador = 0;
for (let i = 0; i < n; i++) contador++;
return contador;
}
console.log(contarHasta(10)); // 10
console.log(contarHasta(1000)); // 1000La función ilustra crecimiento lineal. Theta predice que duplicar la entrada multiplica aproximadamente por dos el número de operaciones principales, no cuánto tardará exactamente en milisegundos.
Para afirmar Θ necesitamos las dos cotas. Si solo conocemos una cota superior, no debemos inventar una inferior. Por ejemplo, saber que un algoritmo es O(n²) no permite concluir que sea Θ(n²): podría ser Θ(n), Θ(n log n) o incluso Θ(1).
Theta completa el vocabulario básico de análisis asintótico al reunir las cotas superior e inferior. En el próximo tema compararemos complejidades para tomar mejores decisiones de diseño.