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

Trimestre 2013 Otoño
Entrega: 9 de septiembre de 2013 en clase.

1. [1 punto] Resuelve exactamente la recurrencia T(1) = 8 y T(n) = 3 T(n-1) - 15 para toda n > 1.
   
2. [1 punto] Resuelve exactamente la recurrencia T(1) = 5 y T(n) = 2 T(n-1) + 3n + 1 para toda n > 1.
3. [1 punto] Resuelve exactamente la recurrencia T(1) = 1 y T(n) = 2 T(n/2) + 6n - 1 para toda n > 1 que sea potencia de 2.
4. [1 punto] Resuelve exactamente la recurrencia T(1) = 3 y T(n) = 4 T(n/3) + 2n - 1 para toda n > 1 que sea potencia de 3.
5. [1 punto] Ordena las siguientes cinco funciones de menor a mayor crecimiento asintótico: n^1/2, 2ⁿ, n log n, n!, ln n.