Page 23 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 23
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
En la figura 1.2 se puede observar gráficamente el crecimiento de las principales funciones de com-
plejidad temporal.
Figura 1.2. Gráfica de las principales funciones de complejidad temporal
cota INferIor aSINtótIca
Si la notación O sirve para indicar una cota superior, también se puede definir una cota inferior.
(g(n)) es el conjunto de todas las funciones f para las cuales existen constantes enteras positivas
i
c y n tales que para cada n > n se cumple lo siguiente:
o o
f(n) cg(n)
i
cg(n) es una “cota inferior” de toda f para toda n> n .
i o
Si el tiempo de ejecución T(n) de un programa es (n ) implica lo siguiente:
2
T(n) > c n ,
2
donde c y n son constantes enteras y positivas.
o
Entonces, T(n) (n ) significa que el programa nunca tardará menos que cn . En la figura 1.3 se
2
2
observa que cg(x) acota por debajo a f(x) a partir de x ; f(n) crece asintóticamente más rápido que
o
g(n) cuando n .
17
