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(cfrac{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(cfrac{n^2}{4}-bfrac{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
