Tarea 1 de Análisis de Algoritmos

Trimestre 2008 Invierno
Entrega: 16 de abril de 2008 en clase.

1. Demuestre por inducción que 1*2 + 2*3 + 3*4 + ... + n(n+1) = n(n+1)(n+2)/3 para toda n >= 0.
2. Demuestre por inducción que n² < 2ⁿ para toda n >= 5.
3. Demuestre que el siguiente algoritmo para calcular y^z es correcto:
   
   x := 1
   mientras z > 0 haz
   
   si z es impar entonces x := xy
   z := z/2 (parte entera)
   y := y²
   
   regresa x
   
4. Suponga que en el algoritmo anterior z tiene n bits. Calcule el número máximo M(n) de multiplicaciones que realiza el algoritmo.
   
5. Para cada una de las siguientes parejas de funciones f(n) y g(n) se tiene que ya sea f(n) es O(g(n)) ó g(n) es O(f(n)) pero no ambas. Diga qué es lo correcto y demuéstrelo:
1. f(n) = n log n, g(n) = n^3/2.
2. f(n) = (log n)², g(n) = n.