Page 24 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 24
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Figura 1.3. Cota inferior asintótica
cota ajuStada aSINtótIca
Si f(n) = (g(n)) y f(n) = O(g(n)), entonces f(n) = (g(n)) si y solo si existen constantes positivas c y
n tal que para toda n > n , C |g(n)| ≤ |f(n)| ≤ C |g(n)|.
o o 1 2
Esto indica que el peor y el mejor caso marcan la misma cantidad de tiempo (figura 1.4).
Figura 1.4. Cota ajustada asintótica
18