Aritmetica de la notacion O

Notación asintótica O grande

Se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una función. La utilidad de aplicar esta notación a un algoritmo es encontrar el limite superior del tiempo de ejecución, es decir el peor caso.

, para todo

Esto significa que la función g(n) pertenece o es valida para f(n) si solo si existen las constantes c y n0, tales que para

Nota: el orden de magnitud de la función será el orden del término de la función mas grande respecto de n.

(PROGRAMA 3)

Ejemplo 1: Supóngase que

cuando n0 = 1 y c =4, n >=1.

Verifique la función utilizando la O grande:

PROGRAMA 4:

cuando n0=0, c=5 para .

PROGRAMA 5:

cuando n0 = 0, c=50 para .