8
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – user340082710 Dec 10 '15 at 2:40
  • $\begingroup$ I am also assuming the final line should read $cn^2$ as opposed to $ck^2$. $\endgroup$ – user340082710 Dec 10 '15 at 2:43
  • $\begingroup$ @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. $\endgroup$ – D. Johnson Dec 10 '15 at 3:02
12
$\begingroup$

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

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.