2.4. Ejemplos.
Ejemplo 5. El tiempo de ejecución de un determinado programa se puede expresar con la siguiente ecuación de recurrencia:
Calcula el tiempo de ejecución para los valores de n que sean potencia de 2. Exprésalo usando las notaciones O, ? ó ?.
Muestra las condiciones iniciales que se deberían aplicar.
Eliminar la condición de que n sea potencia de 2.
La afirmación t(n) ? ?(log n) ¿es correcta en este caso?, ¿es una buena cota para el orden de complejidad del programa?
2t(?n/2?) + 3t(?n/4?) + 2n + 1 En otro caso