Cota inferior asintótica

Keywords: Cota inferior asintótica, Cota ajustada asintótica, Cota superior asintótica, Teoría de la complejidad computacional, Análisis de algoritmos

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:

$\Omega(g(x)) = \left\{\begin{matrix} f(x) : \mbox{existen } c,x_0 \mbox{ constantes positivas tales que} \\ \forall x:x_0\le x: 0\le cg(x)\le f(x) \end{matrix}\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$ f(x) no supera $c g (x)$ . Quiere decir que la función f es superior a g a partir de un valor dado salvo por una 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.

thumb|244px|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 $c g (x)$ con respecto a f(x) cuando x tiende a infinito.

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

f (x) = Θ(g (x)) si y solo si f (x) = O (g (x)) y f (x) = Ω(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≥0 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².

Bibliografía

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