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:

constantes positivas tales que

{\displaystyle \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}\leq x:0\leq c_{1}g(x)\leq f(x)\leq c_{2}g(x)\end{matrix}}\right\}}

Una función f(x) pertenece a Θ(g(x)) cuando existen constantes positivas

tales que a partir de un valor

f(x) se encuentra atrapada entre

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

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))\,}