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

Trimestre 2016 Otoño
Entrega: 10 de octubre de 2016 en clase.

1. [2 puntos] Demuestra que el siguiente algoritmo iterativo para calcular la exponenciación y^z es correcto:
   
   potencia(y, z)
   

   1. x := 1
   2. mientras z > 0
   1. x := x*y
   2. z := z-1
   3. regresa x
2. [2 puntos] Demuestra que el siguiente algoritmo recursivo para calcular la exponenciación y^z es correcto:
   
   potencia(y, z)
   

   1. si z = 0 entonces regresa 1
   2. si z es impar entonces regresa potencia(y², z/2)*y
   3. en caso contrario regresa potencia(y², z/2)
   Debes suponer que la división z/2 regresa sólo la parte entera de la división.
3. [1 punto] Ordena las siguientes cinco funciones de menor a mayor crecimiento asintótico: 100n^1/2, 4ⁿ, n² log n, n!, log₂ n.