Aritmetica de la notacion O

*Notacion asintotica "O" grande: se usa para hacer referencia a la velocidad de crecimiento de los valores de una funcion. La utilidad de aplicar esta notacion a un algoritmo es encontrar el limite superior del tiempo de ejecucion, es decir, el peor caso.
=Definicion= |g(n)|<=|c.f(n)|, para todo n>n0.

Esto signofica que la funcion g(n) pertenece o es valida para f(n) si i solo si existen las constantes c y n0 tales que para n>=n0 T(n)<=cn

El orden de magnitud de la funcoin sera el orden del termino de la funcion mas grande respecto de n.

Ej. 1: Suponga que T(n)=(n+1)al cuadr cuando n0=1 y c=4 para n>=1. Verifique la funcion usando la "O" grande.
(n+1)2 <=cn2
(1+1)2<=4(1)2
2~2<4
4<=4

Existe una notación similar para indicar la mínima cantidad de recursos que un algoritmo necesita para alguna clase de entrada. La cota inferior de un algoritmo, denotada por el símbolo Ω, pronunciado “Gran Omega” u “Omega”, tiene la siguiente definición:

• T(n) está en el conjunto Ω (g(n)), si existen dos constantes positivas c y n0 tales que
|T(n)| ≥ c|g(n)| para todo n > n0.
• Ejemplo: Si T(n)=c1n2+c2n para c1 y c2 > 0, entonces:
|c1n2+c2n|≥|c1n2|≥c1|n2|
Por lo tanto, T(n) está en
Ω(n2).