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 substitution 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, there is no way to solve $cn^2- bn^2 + n^2 \leq cn^2 - bn^2 $ for $b$

  • 4
    $\begingroup$ Are you sure it's in $\Theta(n^2)$? $\endgroup$
    – mrk
    Sep 19 '12 at 12:29
  • $\begingroup$ very sure, it is taken right from the book $\endgroup$
    – newprint
    Sep 19 '12 at 14:27
  • 4
    $\begingroup$ The solution is $\Theta(n^2 \log n)$. Try proving that by the substitution method. $\endgroup$
    – mrk
    Sep 19 '12 at 17:23

If you're using the same book I have (Introduction to Algorithms 3rd edition), then you mis-wrote the question. The relation in question should be: $T(n)=4T(n/2) + n.$

That said, substitution here won't work, as you know. Assuming $T(n) \le cn^2,$ you get:

$T(n)\le4T(n/2) + n$

$T(n)\le4(c\frac{n^2}{4}) + n$

$T(n)\le cn^2 + n$

Which doesn't imply $T(n) < cn^2.$ Instead, you can make the assumption: $T(n) \le cn^2 - bn.$

$T(n)\le4T(n/2) + n$

$T(n)\le4(c\frac{n^2}{4}-b\frac{n}{2}) + n$

$T(n)\le cn^2 + n(-2b + 1)$

Letting $b=1,$ you get an equation consistent with the initial asumption. Namely:

$T(n)\le cn^2 - n$

As a side note, the relation you initially wrote, $T(n)=4T(n/2) + n^2,$ can be solved using case 2 of Master's Theorem, and has an answer of $\Theta(n^2lg(n))$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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