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

Más formalmente se define:

$O(g(x))\; =\; \backslash left\backslash \{\backslash begin\{matrix\}\; f(x)\; :\; \backslash mbox\{existen\; \}\; c,x\_0\; \backslash mbox\{\; constantes\; positivas\; tales\; que\}\; \backslash \backslash \; \backslash forall\; x:x\_0\backslash le\; x:\; 0\backslash le\; f(x)\backslash le\; cg(x)\; \backslash end\{matrix\}\backslash right\backslash \}$

Una función f(x) pertenece a O(g(x)) cuando existe una constante positiva c tal que a partir de un valor $x\_0$ f(x) no sobrepasa a $cg(x)$. Quiere decir que la función f es inferior a g a partir de un valor dado salvo por una factor constante.

La cota superior asintótica tiene gran importancia en Teoría de la complejidad computacional a la hora de definir las clases de complejidad.

CotaSuperiorAsintotica.png A pesar de que O(g(x)) está definido como un conjunto, se acostumbra escribir f(x)=O(g(x)) en lugar de f(x)∈O(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 la las cotas superior e inferior asintóticas (notación Ω):

$f(x)=\backslash Theta(g(x))\; \backslash mbox\{\; si\; y\; solo\; si\; \}\; f(x)=O(g(x))\; \backslash mbox\{\; y\; \}\; f(x)=\backslash Omega(x)$

Ejemplos

• La función x+10 puede ser acotada superiormente por la función x². Para demostrarlo basta notar que para todo valor de x≥1 se cumple x+10≤11x². Por tanto x+10 = O(x²) (sin embargo, x² no sirve como cota inferior para x+10).
• La función x²+200x está acotada superiormente por x². Quiere decir que cuando x tiende a infinito el valor de 200x se puede despreciar con respecto al de x².

Órdenes usuales para funciones

Los órdenes más utilizados en análisis de algoritmos, en orden creciente, son los siguientes (donde c representa una constante):

Bibliografía

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

Análisis matemático | Complejidad computacional

Big O notation | 대문자 O 표기법 | Notacja dużego O | O-большое | สัญกรณ์โอใหญ่ | 大O符号