Cota ajustada asintótica

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:

${displaystyle Theta (g(x))=left{{egin{matrix}f(x):{mbox{existen }}c_{1},c_{2},x_{0}{mbox{ constantes positivas tales que}}\forall x:x_{0}leq x:0leq c_{1}g(x)leq f(x)leq c_{2}g(x)end{matrix}} ight}}$

Una función f(x) pertenece a Θ(g(x)) cuando existen constantes positivas ${displaystyle c_{1}}$ y ${displaystyle c_{2}}$ tales que a partir de un valor ${displaystyle x_{0}}$ f(x) se encuentra atrapada entre ${displaystyle c_{1}g(x)}$ y ${displaystyle 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.

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 cómo se comportan ${displaystyle c_{1}g(x)}$ y ${displaystyle c_{2}g(x)}$ con respecto a f(x) cuando x tiende a infinito.

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

${displaystyle f(x)=Theta (g(x)){mbox{ si y solo si }}f(x)=O(g(x)){mbox{ y }}f(x)=Omega (g(x)),}$

---