Tarea 3 de Análisis y Diseño de Algoritmos

Trimestre 2016 Primavera
Entrega: 2 de junio de 2016 en clase.

  1. [1 punto] Resuelve exactamente la ecuación de recurrencia T(1) = 8 y T(n) = 3 T(n-1) - 15 para toda n > 1.
  2. [1 punto] Resuelve exactamente la ecuación de recurrencia T(1) = 2 y T(n) = T(n-1) + n - 1 para toda n > 1.
  3. [1 punto] Resuelve exactamente la ecuación de recurrencia T(1) = 1 y T(n) = 2 T(n-1) + n - 1 para toda n > 1.
  4. [1 punto] Resuelve la ecuación de recurrencia T(1) = 4 y T(n) = 2 T(n/2) + 3n + 2 para toda n > 1 que sea potencia de 2.
  5. [1 punto] Resuelve la ecuación de recurrencia T(1) = 3 y T(n) = 4 T(n/3) + 2n - 1 para toda n > 1 que sea potencia de 3.
Para las dos últimas puedes usar el teorema general visto en clase, pero sólo obtendrás medio punto.