1.2 Notacion aritmetica "O" grande

Se usa para el analisis de algoritmos mide la eficiencia de un algoritmo conforme crece el tamaño

Ejemplo: T(n)=CN
C -> Tiempo que lleva examinar una variable.

int maximo(int arreglo, int n)
{
int mayor=0;
for(int i=0; imayor)
mayor=arreglo[i];
return mayor;
}
}

Se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una funcion, ignora los valores constanteses decir no toma en cuenta si se hace una mejor o peor implementacion del algoritmo y es independiente de los datos de entrada al algoritmo su utilidad radica en encontrar un limite superior del tiempo de ejecucion es decir el peor caso.

Formula:
g(n) <= cf(n), para todo n>=n

Significa que existen constantes enteros positivos C y No , tales que para n>=No, se cumple la funcion

T(n)<=CN Ejemplo: Supongase que T(n)=(n+1)'2, No=1, C=4 verificar que se cumple la funcion para todo n>=1

• Programa 1: El orden de magnitud de la funcion es el orden del termino mas grande respecto de n (n+1)'2 <= 4(n)'2

T(2) (2+1)'2 <= 4(2)'2 9 <= 16

• Programa 2: Funcion T(n)= 3n'3 + 2n'2 + 10, cuando No=1 y C=5 , verificar para n>=1