La notación Ω expresa una cota inferior asintótica: indica que una función crece al menos tan rápido como otra, salvo por un factor constante y para entradas suficientemente grandes.
Big-O responde «¿qué tan rápido puede crecer como máximo este costo?». La notación Ω responde la pregunta complementaria: «¿qué cantidad de trabajo es inevitable, como mínimo, para esta función o problema?».
Las cotas inferiores muestran límites. Si demostramos que un problema requiere Ω(n) operaciones bajo cierto modelo, sabemos que ningún algoritmo dentro de ese modelo puede resolverlo en tiempo constante o logarítmico para todas las entradas.
La función g(n) es una cota inferior. A partir de n0, f(n) nunca queda por debajo de c veces g(n). La constante c absorbe diferencias de escala que no cambian la tasa de crecimiento.
Si T(n) es Ω(n), existe trabajo proporcional a n que no puede evitarse en el escenario o modelo analizado. No significa que T(n) sea exactamente n ni que todos los casos ejecuten el mismo número de operaciones.
Demostremos que f(n) = 3n² + 7n + 12 pertenece a Ω(n²).
La misma función es O(n²). Tener ambas cotas del mismo orden permitirá afirmar que es Θ(n²).
Ω no significa automáticamente mejor caso, así como O no significa automáticamente peor caso. Las notaciones acotan una función; esa función puede representar el tiempo de mejor, peor o caso promedio, o el espacio usado.
| Concepto | Pregunta |
|---|---|
| Mejor caso | ¿Cuál es el menor costo entre entradas de tamaño n? |
| Peor caso | ¿Cuál es el mayor costo entre entradas de tamaño n? |
| Ω(g(n)) | ¿Qué cota inferior cumple una función de costo elegida? |
| O(g(n)) | ¿Qué cota superior cumple una función de costo elegida? |
El peor caso de búsqueda lineal es O(n) y Ω(n); su mejor caso es O(1) y Ω(1).
Una función puede tener muchas cotas inferiores correctas. Si f(n) es Ω(n²), también es Ω(n), Ω(log n) y Ω(1). Sin embargo, una cota débil aporta poca información sobre su crecimiento real.
En análisis se busca una cota inferior ajustada cuando puede demostrarse, en especial para conocer límites inherentes de un problema.
Para decidir si un valor aparece en un arreglo no ordenado, un algoritmo puede verse obligado a inspeccionar todos los elementos. Si no encuentra el valor en las primeras n - 1 posiciones, aún no puede saber si está en la última.
La cota surge de la falta de información sobre los elementos no inspeccionados, no solo de la forma particular de la búsqueda lineal.
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([3, 8, 12, 17, 24], 3)); // { indice: 0, comparaciones: 1 }
console.log(buscarLineal([3, 8, 12, 17, 24], 99)); // { indice: -1, comparaciones: 5 }El ejemplo muestra mejor y peor caso. La cota Ω(n) anterior se refiere al peor caso del problema de búsqueda sobre datos no ordenados.
Para encontrar el máximo de n números distintos debemos comparar cada elemento, salvo uno, con algún otro. Si un elemento no participara en ninguna comparación, podría ser mayor que todos los demás sin que el algoritmo lo detectara.
Un recorrido lineal alcanza esta cota con n - 1 comparaciones. En el modelo de comparación, es óptimo respecto del orden de crecimiento.
function maximoConConteo(numeros) {
let mayor = numeros[0];
let comparaciones = 0;
for (let i = 1; i < numeros.length; i++) {
comparaciones++;
if (numeros[i] > mayor) mayor = numeros[i];
}
return { mayor, comparaciones };
}
console.log(maximoConConteo([7, 2, 11, 4, 9]));
// { mayor: 11, comparaciones: 4 }Para un arreglo de longitud 5 se realizan cuatro comparaciones. En general se realizan n - 1, igualando la cota inferior.
Si los datos están ordenados y solo se permiten comparaciones, la búsqueda puede usar información adicional para descartar grandes bloques. La cota inferior de peor caso pasa a ser Ω(log n), y la búsqueda binaria la alcanza.
La mejora se debe al orden de los datos. Si el arreglo no estaba ordenado, el costo de ordenarlo debe incluirse en el análisis total.
Un algoritmo de ordenamiento que utiliza únicamente comparaciones debe distinguir entre n! posibles órdenes iniciales de n elementos distintos. Cada comparación crea una decisión en un árbol binario.
La restricción «por comparación» es esencial. Algoritmos que explotan un rango acotado de claves, como counting sort, no quedan sujetos a esta misma barrera.
Una cota inferior puede aplicarse a un algoritmo específico o a todo un problema bajo un modelo de cómputo. Debemos indicar qué estamos afirmando.
| Tipo | Ejemplo |
|---|---|
| Sobre un algoritmo | Este recorrido examina n elementos, por lo tanto su tiempo es Ω(n). |
| Sobre un problema | Encontrar el máximo requiere Ω(n) comparaciones en el peor caso. |
| Con modelo | Ordenar por comparación requiere Ω(n log n) comparaciones. |
Las cotas del problema son más fuertes porque establecen que no existe una solución asintóticamente mejor dentro de las reglas indicadas.
Omega también se aplica a memoria. Si un algoritmo debe devolver una copia explícita de n elementos, necesita espacio proporcional a n para contener la salida, aunque sus cálculos internos sean eficientes.
Al analizar memoria conviene especificar si contamos entrada, salida y espacio auxiliar. Cada convención responde una pregunta distinta.
La prueba formal se parece a la de Big-O, pero la desigualdad se invierte. Para demostrar que 5n² - 2n pertenece a Ω(n²), buscamos una constante positiva que quede por debajo de la función para n grande.
Las recurrencias también permiten obtener cotas inferiores. Si T(n) = 2T(n/2) + n, el trabajo de la raíz ya da Ω(n). Además, cada nivel del árbol aporta n y hay log n niveles, por lo que se obtiene una cota más ajustada Ω(n log n).
Ejecutar un programa y observar que revisó todos los elementos para una entrada no demuestra una cota inferior universal. Para probar Ω debemos razonar sobre una familia de entradas o sobre la información que cualquier algoritmo necesita obtener.
function comparacionesParaMaximo(n) {
return Math.max(0, n - 1);
}
console.log(comparacionesParaMaximo(1)); // 0
console.log(comparacionesParaMaximo(10)); // 9La función muestra el conteo de un algoritmo lineal. El razonamiento de la sección 20.9 es el que establece que n - 1 comparaciones son inevitables.
Omega muestra el trabajo que no podemos evitar. En el próximo tema combinaremos cotas superiores e inferiores con la notación Θ (Theta), que describe órdenes de crecimiento ajustados.