Quick Recurrences Question [closed]

$$given: T(n)=4T(n/2)+n^2 ;T(1)=1\\=4[4T(n/2^2 )+(n/2)^2 ]+n^2\\=4^2 [4T(n/2^2 )+(n/2)^2 ]+n^2+n^2\\=4^3 [4T(n/2^3 )+(n/2)^2 ]+n^2/4+n^2+n^2\\…\\=4^k T(n/2^k )+$$

Here is where I'm stuck because I'm unsure what the sequence at the end should be?

• It should end when $n/2^{k}\leq 1$ or about $\log_{2}(n)$ subdivisions. Apr 10, 2015 at 19:47
• Yes, I know that, but I'm not sure what the end of the statement using k would be Apr 10, 2015 at 19:50
• $k$ will be (approximately) $\log_{2}(n)$, that is because $n/2^{k}\approx 1$, so solve for $k$... Apr 10, 2015 at 19:52
• This recurrence was discussed at this MSE link. Apr 10, 2015 at 20:20

\begin{align} T(n)&=4T\left(\frac{n}{2}\right)+n^2 && \text{Original.}\\ T(n)&=4\left(4T\left(\frac{n}{2^2}\right) + \frac{n^2}{2^2}\right) + n^2 &&\text{First iteration.} \\ T(n)&=4^2T\left(\frac{n}{2^2}\right) + n^2 + n^2 &&\text{After distributing.} \\ T(n)&=4^2\left( 4T\left(\frac{n}{2^3}\right) +\frac{n^2}{4^2}\right) + n^2 + n^2 &&\text{Second iteration.} \\ T(n)&=4^3 T\left(\frac{n}{2^3}\right) + n^2 + n^2 + n^2 &&\text{After distributing.} \\ &\vdots \\ T(n)&=4^k T\left(\frac{n}{2^k}\right) + kn^2. \end{align} Take $n=2^k$, then $\lg n = k$, and so $T(n) = 4^{\lg n} + n^2 \lg n$.
Since $a^{\log_n b} = b^{\log_n a}$, then we can show that $T(n) = \Theta(n^2\lg n)$ for powers of $2$.
I won't show it here, but we could also play around with some inequalities, and show that $T(n) = \Theta(n^2\lg n)$ for all natural $n$ actually.
• In the second iteration, why did it become $n^2/4^2$ instead of $n^2/2^2$? Apr 10, 2015 at 19:58
• Look at the original equation. What happens when $n\mapsto \frac{n}{4}$? The argument of $T$ becomes $\frac{n}{8}$, i.e. $\frac{n}{2^3}$, while the hanging $n^2$ becomes $\left(\frac{n}{4}\right)^2$. Apr 10, 2015 at 20:04