Tarea 2 de Análisis de Algoritmos

Trimestre 2012 Primavera
Entrega: 29 de mayo de 2012 en clase.

1. [2 puntos] Ordena las siguientes cinco funciones de menor a mayor crecimiento asintótico: n^1/2, 2ⁿ, n log n, n!, ln n.
2. [4 puntos] Sea f(n) = (n² - n)/2 y g(n) = 6n. Demuestra que f(n) es O(g(n)) o que g(n) es O(f(n)), lo que sea verdadero.
3. [4 puntos] Sea f(n) = 2ⁿ - n² y g(n) = n⁴ + n². Demuestra que f(n) es O(g(n)) o que g(n) es O(f(n)), lo que sea verdadero.
4. [2 puntos] Resuelve exactamente la recurrencia T(1) = 1 y T(n) = 3 T(n-1) + 2 para toda n > 1.
5. [3 puntos] Resuelve exactamente la recurrencia T(1) = 1 y T(n) = 2 T(n-1) + n - 1 para toda n > 1.
6. [5 puntos] Resuelve exactamente la recurrencia T(1) = 1 y T(n) = n T(n-1) + n para toda n > 1.
7. [20 puntos] Resuelve el examen eliminatorio del Noveno Concurso de Programación de la UAM. Esta parte se deberá entregar según lo indique el enunciado del examen. La calificación que obtengas en el examen eliminatorio se dividirá entre 9 para acumularla a esta tarea.

Resultados del examen eliminatorio