Page 207 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

cota SuperIor aSINtótIca

Para denotar la cota superior asintótica de una función g (n) se escribe 0 (f (n)) como el conjunto de
funciones:

Es decir, O (g (n)) es el conjunto de funciones con dominio e imagen en los números naturales, tales
que existe una constante mayor a cero, donde a partir de un número natural el crecimiento de g
(n) es menor o igual al de la función cf (n). Dado que se está trabajando con conjuntos la notación
correcta debe ser Pero en la literatura y para facilitar el análisis, se emplea el
símbolo de igualdad para indicar que la función es un elemento del conjunto. Esto es, que tanto
como representan lo mismo.

Por ejemplo, sea g (n) = 5n - 10n +1, entonces:
2

Esta notación se emplea para indicar la cota superior de una función, dentro de un factor constante.

cota INferIor aSINtótIca

Para denotar la cota inferior asintótica de una función g (n) se escribe (f (n)) como el conjunto de
funciones:

Es decir, g (n) es el conjunto de funciones con dominio e imagen en los números naturales, tales
que existe una constante mayor a cero, donde a partir de un número natural n el crecimiento de f (n)
0
es menor o igual al de la función cg (n). Al igual que con el conjunto O (g (n)), para facilitar el análisis,
se emplea el símbolo de igualdad para indicar que la función es un elemento del conjunto. Esto es,
que tanto g (n) (f (n))como g (n) = (f (n)) representan lo mismo.

201