-1
$\begingroup$

$$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?

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

1 Answer 1

1
$\begingroup$

It helps to keep powers intact and to distribute after each iteration.

$$\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.

$\endgroup$
3
  • $\begingroup$ In the second iteration, why did it become $n^2/4^2$ instead of $n^2/2^2$? $\endgroup$
    – dms94
    Apr 10, 2015 at 19:58
  • $\begingroup$ 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$. $\endgroup$ Apr 10, 2015 at 20:04
  • $\begingroup$ Oh right, got it, thank you! $\endgroup$
    – dms94
    Apr 10, 2015 at 20:06

Not the answer you're looking for? Browse other questions tagged .