Unidad I Notaciones Aritmeticas

Unidad 1

1.2 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 pertenece o es valida para si solo si existen las constantes C y no 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.

Notación Omega grande:
Se dice que f(n) es omega grande de g(n) si existen las constantes positivas C y no tales que f(n)>=g(n) para todo

Para cualesquiera de las dos funciones f(n) y g(n) definidas anteriormente se tiene que
f(n) = Omega grande( g(n) ) si y sólo si g(n) = O( f(n) ).

F(n)=O si y solo si g(n)=O(f(n))
La función omega grande se utiliza para especificar una cota inferior para la velocidad de crecimiento de una función f(n) cuando esta en función de n. Y se usa la notación T(n) es omega grande(g(n)) y significa que existe una constante c tal que t(n)>=c(g(n)) para un numero infinito de valores n.