Tarea 2 de Análisis de Algoritmos

Trimestre 2012 Otoño
Entrega: 2 de octubre de 2012 en clase.

1. [5 puntos] En un montículo cada nodo es menor o igual que sus hijos. Demuestra por inducción en la altura del montículo que cada nodo es menor o igual que sus descendientes.
2. [10 puntos] Dibuja la construcción de un montículo al que se le insertan los elementos 10, 2, 9, 16, 8, 6, 1, 3, 12, 5 en ese orden.
3. [5 puntos] Resuelve exactamente la recurrencia T(1) = 1 y T(n) = 3 T(n-1) + n - 1 para toda n > 1.
4. [10 puntos] Resuelve exactamente la recurrencia T(1) = 1 y T(n) = 2n T(n-1) + n para toda n > 1.
5. [10 puntos] Ordena las siguientes diez funciones de menor a mayor crecimiento asintótico: n², 3ⁿ, n log n, n!, ln n, n, 2ⁿ, log log n, 0.5ⁿ, n^-1.