Objetivo: predecir el comportamiento del algoritmo.
Aspectos cuantitativos:
- tiempo de ejecución
- cantidad de memoria
Se dispone de una medida de la eficiencia teórica y no exacta (utilizada para aproximar, clasificar y comparar algoritmos).
Acotar T(n), siendo n el tamaño del problema (a veces, la entrada). Cuando n → ∞ se considera comportamiento asintótico.
T(n) = O(f(n)) → f(n) es una cota superior, que crece más deprisa que T(n).
Establece un orden relativo entre las funciones, comparando la tasa de crecmiento.
Se omite por simplicidad que las tres constantes tienen que ser estrictamente superiores a 0.
Si T(n) es un polinomio de grado k, se tiene una cota exacta Θ(n^k).
Otra utilidad, la siguiente:
La suma equivale al máximo de los sumandos, el producto se opera como producto normal.
Comparación de las posibles cotas.
Cotas comunes:
Gráfico de las cotas comunes:
Para resolver recurrencias de divide y vencerás podemos ayudarnos de la siguiente regla.
