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

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

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

Notación

Esta notación se emplea para denotar al conjunto de funciones cuyo orden de crecimiento es el
mismo. Para denotar que una función g (n) tiene el mismo orden de crecimiento de un conjunto de
funciones se escribe de este modo:

Esto es significa que g (n) (f (n) si existen constantes positivas c y c tales que la “mantienen”
1 2
entre c f(n) y c f (n) para un suficientemente grande. Al igual que con los conjuntos O (g (n)) y , (g
1 2
(n)) para facilitar el análisis, se emplea el símbolo de igualdad para indicar que la función es un ele-
mento del conjunto. Esto es, que tanto g (n) (f (n)) como g (n) = ( fn)) representan lo mismo.
Otra forma de establecer que g (n) (f (n)) es que se cumpla la siguiente condición:

De los ejemplos anteriores donde g (n) = 5n - 10n +1 se puede decir que:
2
•

Notación asintótica justa

La notación asintótica 0 (f (n)) puede o no ser asintóticamente justa. Por ejemplo, la cota 3 0 n2n =
2
(n ) es asintóticamente justa, pero la cota 3 n = no lo es. De aquí que se emplea la notación o (f (n))
2
2
para denotar una cota superior que no es asintóticamente justa. Formalmente se define o (f (n)),
pequeña o de f (n) , de este modo:

202