0
$\begingroup$

Substation method fails to prove that $T(n) = \Theta(n^2) $ for the recursion $T(n)= 4T(n/2) + n^2$, since you end up with $T(n) < cn^2 \leq cn^2 + n^2 $.

I don't understand how to subtract off lower-order term to prove that substation works.
Came up with: $T(n) \leq cn^2 - bn^2$ Assume it holds for $T(n/2) \leq c(n/2)^2 - b(n/2)^2$
$T(n) \leq 4(c(n/2)^2 - b(n/2)^2) + n^2 = cn^2- bn^2 + n^2 $
However, you there is no way to solve $cn^2- bn^2 + n^2 \leq cn^2 - bn^2 $ for $b$

But I am not sure if I am going in the right direction, though mathematics is very elementary. Thanks !

2 Answers 2

2

$T(n)=4T(n/2)+n^2=4(4T(n/4)+n^2/4)+n^2=16T(n/4)+2n^2=16(T(n/8)+n^2/16)+2n^2=16T(n/8)+3n^2=\cdots=2^{i+1}T(n/2^i)+in^2$

You can follow it till $2^i\approx n\implies $ Number of terms i= $\lfloor\log_2 n\rfloor\implies T(n)\approx nT(1)+n^2\log_2n$ which is surely not $\Theta(n^2)$ but $\Theta(n^2\log_2n)$

1

If you can actually prove that there’s a positive constant $c$ such that $T(n), you’re practically done. It’s obvious from the recurrence that $T(n)\ge n^2$, so you would have $n^2\le T(n), which says that $T(n)$ is $\Theta(n^2)$. However, I seriously doubt that you can do so.