2.1. Introducción.
Conclusión: Estudiar la variación del tiempo y la memoria necesitada por un algoritmo respecto al tamaño de la entrada y a los posibles casos, de forma aproximada (y parametrizada).
Ejemplo. Algoritmo anterior. Conteo de instrucciones.
- Mejor caso. Se encuentra x en la 1ª posición:
Tiempo(N) = a
- Peor caso. No se encuentra x:
Tiempo(N) = b·N + c
- Caso medio. Se encuentra x con probabilidad P:
Tiempo(N) = b·N + c - (d·N+e)·P