## 1.3.2 MÉTODO DE ITERACIONES

Para resolver una relación de recurrencia asociada a la sucesión: a0,a1,a2 por iteración, utilizamos la relación de recurrencia para escribir el n-ésimo término an en términos de algunos de sus predecesores. Luego utilizamos de manera sucesiva la relación de recurrencia para reemplazar cada uno de los términos por algunos de sus predecesores. Continuamos hasta llegar a alguno de los casos base.

Ejemplo, dada la recurrencia:

T(n)=3T(n/4)

= n + 3T(n/4)

= n + 3((n/4) + 3T(n/16))

= n + 3((n/4)+ 3T(n/16)+ 3T(n/64))

= n + 3((n/4) + 9T(n/16) + 27(n/64))

=O(n)

Características

- No requiere adivinar la respuesta.
- Puede requerir más álgebra que el de substitución.
- Expande (itera) la recurrencia y la expresa como sumatoria de términos dependientes de n y las condiciones iniciales.
- Después usa técnicas para evaluar sumatorias para dar cotas a la solución.
- Puede ser difícil resolver recurrencias con este método.
  - A veces al iterar la recurrencia, adivinamos una solución y seguimos con el método de sustitución.

###