Problem Detail: This question is fairly specific in the manner of steps taken to solve the problem. Given $T(n)=2T(2n/3)+O(n)$ prove that $T(n)=O(n^2)$. So the steps were as follows. We want to prove that $T(n) le cn^2$. $$begin{align*} T(n)&=2T(2n/3)+O(n) &leq 2c(2n/3)^2+an &leq (8/9)(cn^2)+an end{align*}$$ and then my prof went on to do: $$T(n) leq cn^2+(an-(1/9)cn^2),,$$ which comes out to: $$T(n)leq cn^2 text{ for any }c >= 9a,.$$ My question is, how were they able to switch from 8/9 to 1/9 while introducing a new term? Is this allowed? She never explained, this was just in her solutions.
Asked By : D. Johnson
Answered By : user340082710
As you pointed out, the reason for splitting the term into two pieces is to be able to cancel the $an$ term. If we go directly from $(8/9)cn^2 + an leq cn^2 + an$, then we get stuck as we cannot do anything with the $an$ term. By splitting it in the way described, this allows the $(1/9)cn^2$ to be larger than $an$ when $c geq 9a$, which then gives you the desired result since $an – (1/9)cn^2 leq 0$ for such values of $c$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/50541
