Terminating the Iteration

T(n) = 3^k T(n/(4^k)) + 4 n (1-(3/4)^k).

For what k does n/(4^k) = 1?

$\begin{eqnarraystar} n/(4^k) &=& 1\\ n &=& (4^k)\\ \log(n) &=& k \log(4)\\ k &=& \log(n)/2\\ \end{eqnarraystar}$

Substituting into the formula above...

$3^k = 3^{\log(n)/2} = n^{\log(3)/2}$
$(3/4)^k = (3/4)^{\log(n)/2} = n^{\log(3)/2-1}$
So,
$\begin{eqnarraystar} T(n) &=& n^{\log(3)/2} T(1) + 4 n (1-n^{\log(3)/2-1}) \\ &... ...4n - 4 n^{\log(3)/2} \\ &=& 4n - 3 n^{\log(3)/2} \\ &=& O(n)\end{eqnarraystar}$

Next: The Table Method Up: SOLVING RECURRENCES Previous: The Iteration Method