Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question


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|cite|improve this answer

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|cite|improve this answer

Your Answer


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.