[Solved]: Big-O proof for a recurrence relation?

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