Cota superior asintótica

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 de Landau O(g(x)) (o coloquialmente llamada Notación O Grande) para referirse a las funciones acotadas superiormente por la función g(x).

Más formalmente se define:

$O(g(x)) = \left\{\begin{matrix} f(x) : \mbox{existen } c,x_0>0\mbox{ tales que} \\ \forall x\ge x_0: 0\le |f(x)|\le c|g(x)| \end{matrix}\right\}$

Una función f(x) pertenece a O(g(x)) cuando existe una constante positiva c tal que a partir de un valor x₀, 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 un 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.

f(x)=O(g(x)).

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. Note además que dicho conjunto es no vacío pues f(x)=O(g(x)).

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

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

Propiedades

Sea $E\subseteq \mathbb{R}$, sean $f_1:E\to \mathbb{R}$, $g_1:E\to \mathbb{R}$, $f_2:E\to \mathbb{R}$, $g_2:E\to \mathbb{R}$ funciones y k un real. Entonces los siguientes enunciados son ciertos

i) Si $f_1 = O(g_1)\,$ y $g_1 = O(g_2)\,$, entonces $f_1 = O(g_2)\,$

ii) Si $f_1=O(g_1)\,$ y $f_2=O(g_2)\,$,entonces $f_1f_2=O(g_1g_2)\,$

iii) $f_2O(g_1)=O(f_2g_1)\,$ (aquí es igualdad entre conjuntos)

iv) Si $f_1=O(g_1)\,$ y $f_2=O(g_2)\,$,entonces $f_1+f_2=O(|g_1|+|g_2|)\,$

v) Si $k\neq 0\,$ entonces $O(g_1)=O(kg_1)\,$ (aquí es igualdad entre conjuntos)

vi) Si $f_1= O(g_1)\,$, entonces $kf_1=O(g_1)\,$.

Ejemplos

• La función x+10 puede ser acotada superiormente por la función 11x². 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, es decir, 11x²≠O(x + 10).
  Observación: Este ejemplo muestra que el uso del símbolo "=" esta mal empleado (matemáticamente) pues la notación de Landau (O grande) no es reflexiva.
• 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 y n el tamaño de la entrada):

notación	nombre
O(1)	orden constante
O(log log n )	orden subalgorítmico
O(log n)	orden logarítmico
O($\sqrt n$)	orden sublineal
O(n)	orden lineal
O(n · log n)	orden lineal logarítmico
O(nc)	orden potencial
O(cn), n > 1	orden exponencial
O(n!)	orden factorial
O(nn)	orden potencial exponencial[cita requerida]

Véase también

• Cota inferior asintótica
• Cota ajustada asintótica
• Notación de Landau

Bibliografía

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