Aritmética de la notación 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 límite superior del tiempo de ejecución, es decir el peor caso.

Definición
|g(n)|<=|c.f(n)|, para todo ne>=n0
Esto significa que la función g(n) pertenece o es válida para f(n) si solo si existen las constantes c y no tales que para n>=n0:
-T(n)<=cn
Nota
El orden de magnitud de la función será el orden del término de la función más grande respecto de n.
Ejemplo 1:
Supóngase que T(n) = (n+1) ^2, n_0=1 y c=4 para n>=1. Verifique la función utilizando la ‘O’ grande.

(n+1)^2<=cn^2

(1+1)^2<=4(1)^2
2^2=4
4<=4

Si se cumple la Función