Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 !

share|improve this question
add comment

2 Answers

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

share|improve this answer
add comment

If you can actually prove that there’s a positive constant $c$ such that $T(n)<cn^2$, 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)<cn^2$, which says that $T(n)$ is $\Theta(n^2)$. However, I seriously doubt that you can do so.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.