Cota inferior asintótica

En análisis de algoritmos una cota inferior asintótica es una función que sirve de cota inferior de otra función cuando el argumento tiende a infinito. Usualmente se utiliza la notación Ω(g(x)) para referirse a las funciones acotadas inferiormente por la función g(x).

Más formalmente se define:

$\mathrm{\Omega }(g(x))=\left\{\begin{array}{c}f(x):\text{existen }c,x_0\text{ constantes positivas tales que}\\ \mathrm{\forall }x:x_0\le x:0\le cg(x)\le f(x)\end{array}\right\}$

Una función f(x) pertenece a Ω(g(x)) cuando existe una constante positiva c tal que a partir de un valor $x_0$, $cg(x)$ no supera f(x). Quiere decir que la función f es superior a g a partir de un valor dado salvo por un factor constante.

La cota inferior asintótica tiene utilidad en Teoría de la complejidad computacional a la hora de calcular la complejidad del mejor caso para los algoritmos.

f(x)=Ω(g(x)).

A pesar de que Ω(g(x)) está definido como un conjunto, se acostumbra escribir f(x)=Ω(g(x)) en lugar de f(x) ∈ Ω(g(x)). Muchas veces también se habla de una función nombrando únicamente su expresión, como en x² en lugar de h(x)=x², siempre que esté claro cual es el parámetro de la función dentro de la expresión. En la gráfica se da un ejemplo esquemático de como se comporta $cg(x)$ con respecto a f(x) cuando x tiende a infinito.

La cota ajustada asintótica (notación Θ) tiene relación con las cotas superior (notación O) e inferior asintóticas :

$f(x)=\mathrm{\Theta }(g(x))\text{ si y solo si }f(x)=O(g(x))\text{ y }f(x)=\mathrm{\Omega }(g(x))$

Ejemplos

• La función x² puede ser acotada inferiormente por la función x. Para demostrarlo basta notar que para todo valor de x≥1 se cumple x≤x². Por tanto x² = Ω(x) (sin embargo, x no sirve como cota superior para x²).
• La función x²+200x está acotada inferiormente por x². Quiere decir que cuando x tiende a infinito el valor de 200x se puede despreciar con respecto al de x².Además de que nunca va a tocar a cero

Véase también

• Cota ajustada asintótica
• Cota superior asintótica
• Notación de Landau

Bibliografía

• Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein