Cota ajustada asintótica

Keywords: Cota ajustada asintótica, Cota inferior asintótica, Cota superior asintótica, Análisis de algoritmos

En análisis de algoritmos una cota ajustada asintótica es una función que sirve de cota tanto superior como 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 por la función g(x).

Más formalmente se define:

$\Theta(g(x)) = \left\{\begin{matrix} f(x) : \mbox{existen } c_1,c_2,x_0 \mbox{ constantes positivas tales que} \\ \forall x:x_0\le x: 0\le c_1g(x)\le f(x)\le c_2g(x) \end{matrix}\right\}$

Una función f(x) pertenece a Θ(g(x)) cuando existen constantes positivas $c 1$ y $c 2$ tales que a partir de un valor $x 0$ f(x) se encuentra atrapada entre $c 1 g (x)$ y $c 2 g (x)$ . Quiere decir que las funciones f y g son iguales a partir de un valor dado salvo por una factor constante. Por tanto tiene sentido tomar a g como un representante de f.

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 la función 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 comportan $c 1 g (x)$ y $c 2 g (x)$ con respecto a f(x) cuando x tiende a infinito.

La cota ajustada asintótica tiene relación con la las cotas superior e inferior asintóticas (respectivamente las notaciones O y Ω):

f (x) = Θ(g (x)) si y solo si f (x) = O (g (x)) y f (x) = Ω(x)

Ejemplos

La función x+10 puede ser acotada por la función x. Para demostrarlo basta notar que para todo valor de x≥1 se cumple g(x)≤h(x)≤11g(x). Por tanto x+10 = Θ(x).
La función x²+200x está acotada de forma ajustada 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