The Iteration Method

The subtitution method is great once you've gotten enough experience to make a good guess at the answer.

The iteration method is a nice way to gain that experience.

\begin{eqnarraystar} T(1) &=& 1 \\ T(n) &=& 3 T(n/4) + n\\ &=& 3 (3 T(n/16) + n... ...um_{i=0}^{k-1} (3/4)^i\\ &=& 3^k T(n/(4^k)) + 4 n (1-(3/4)^k)\end{eqnarraystar}

next up previous
Next: Terminating the Iteration Up: SOLVING RECURRENCES Previous: Making Good Guesses