Subtracting lower-order term to prove subtitution method works

Problem Detail: 

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$

Asked By : newprint

Answered By : Cookyt

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4612