$$n \mathrm{\ is \ power \ of \ 2,\ } T(n)=\{^{1, \ n=1}_{4T(\frac{n}{2})+cn,\ n>1}$$
I did the following to find the big-theta of T(n).
(i): $T(n)=4T(\frac{n}{2})+cn \\ \ \ \ \ \ \ \ =4[4T(\frac{n}{2^2})+cn]+cn\\ \ \ \ \ \ \ \ =4^2T(\frac{n}{2^2})+4cn+cn\\ \ \ \ \ \ \ \ \ ...\\ \ \ \ \ \ \ \ =4^{\log_2n}T(\frac{n}{2^{\log_2n}})+(cn)\sum_{i=0}^{\log_2n-1}4i\\ \ \ \ \ \ \ \ =n^2T(1)+(cn)\left[\frac{4^{\log_2n}-1}{4-1} \right]\\ \ \ \ \ \ \ \ =n^2+\frac{cn}{3}(n^2-1)\\ \ \ \ \ \ \ \ =n^2+\frac{cn^3}{3}-\frac{cn}{3}
\\ \ \ \ \ \ \ \ =\Theta(n^3)$
(ii). $\mathrm{Assume \ n=2^j}\\ T(n)=T(2^j)\\ \ \ \ \ \ \ \ =4T(2^{j-1})+2^jc\\ \ \ \ \ \ \ \ =4[4T(2^{j-2})+2^{j-1}c]+2^jc \\ \ \ \ \ \ \ \ =4^2T(2^{j-2})+2 \cdot 2^jc+2^jc
\\ \ \ \ \ \ \ \ =4^2[4T(2^{j-3})+2^{j-2}c]+2\cdot2^jc+2^jc \\ \ \ \ \ \ \ \ = 4^3T(2^{j-3})+2^2 \cdot2^jc+2\cdot2^jc+2^jc \\ \ \ \ \ \ \ \ \ ...\\ \ \ \ \ \ \ \ =4^jT(1)+2^jc\sum_{i=0}^{j-1}2^i \\ \ \ \ \ \ \ \ =2^{2j}+2^jc(2^j-1)\\ \ \ \ \ \ \ \ =2^{2j}+2^{2j}c-2^jc \\ \ \ \ \ \ \ \ =n^2+Cn^2-cn \\ \ \ \ \ \ \ \ =(1+c)n^2-cn \\ \ \ \ \ \ \ \ =\Theta(n^2)$
And $\Theta(n^2)$ is the correct answer.
May I know where did i do it wrong? THX!
In the second line of the first derivation, you replaced 'n' with 'n/2' in the argument to T() but NOT in the 'cn' part. You made the same mistake on each successive line.