# Big-O proof for a recurrence relation?

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.

• I don't see a new term introduced? We have that $cn^2 +an - (1/9)cn^2$ simplifies to $(8/9)cn^2 + an$ as in the line before. So the two lines are actually equal. Perhaps you're asking why one might want to do this? – user340082710 Dec 10 '15 at 2:40
• I am also assuming the final line should read $cn^2$ as opposed to $ck^2$. – user340082710 Dec 10 '15 at 2:43
• @ZacharyFrenette Ah you're right. in that case, i wasnt sure how she did the simplification. Why would one choose to separate the terms in that way? there are many ways to split (8/9). I think know why one would want to do this, to cancel out that extra $an$? Otherwise the inequality won't hold. Also thanks for pointing out the typo, will fix. if you'd like to comment as an answer, i can accept it. – D. Johnson Dec 10 '15 at 3:02

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