2
$\begingroup$

For example, say I want to analyze $T(n)=3T(\lfloor n/3 \rfloor )+2n$ for $n>2$, and $T(n)=1$ otherwise. This is clearly $O(n\log n)$; however it seems that with induction you can prove it is $O(n)$:

Base case: $T(1)$ is $O(1)$, $T(2)$ is $O(2)$

Inductive step: $T(n) = 3\times O(n/3) + 2n \in O(n)$

Where does this go wrong? Why can I do this? Induction clearly is a valid technique, but what subtlety of $O$ causes me to be able to prove a wrong bound?

$\endgroup$
  • $\begingroup$ I've not checked the specific recurrence you're talking about but note that any function that is $O(n)$ is also $O(n\log n)$. $\endgroup$ – David Richerby Jan 31 '14 at 16:53
  • 2
    $\begingroup$ You call that a paradox? Wrap your think brain around $O(n) = n = 1 + 1 + ... + 1 = O(1) + O(1) + ... + O(1) = O(1)$. $\endgroup$ – Patrick87 Jan 31 '14 at 17:02
  • 1
    $\begingroup$ That's a not a paradox, you are falling victim to widespreach abuse of notation on one hand and sloppy proof on the other hand. See the linked question for particulars. $\endgroup$ – Raphael Jan 31 '14 at 17:20
  • $\begingroup$ I was trying to be unsloppy by avoiding the $=$ sign... $\endgroup$ – ithisa Jan 31 '14 at 17:25
  • $\begingroup$ @Raphael : can you please explain why this is wrong in an answer? I am not really fond of just memorizing things like "carry around a constant" without knowing why. $\endgroup$ – ithisa Jan 31 '14 at 17:27
2
$\begingroup$

You have to carry around the big-O constant. Suppose that we are trying to prove that $T(n) \leq Cn$. In the inductive step, we have $$ T(n) \leq 3C\lfloor n/3 \rfloor + 2n \leq (C+2)n. $$ So we are not able to maintain the constant $C$. Let's have another go, with $T(n) \leq C_nn$. The argument above shows that we can put $C_n = C_{\lfloor n/3 \rfloor} + 2$, and so $C_n = O(\log n)$ works, and we get the correct asymptotics $O(n\log n)$. (To know that this is tight, we would also need a lower bound, proved in much the same way, with some minor technicalities stemming from the floor.)

$\endgroup$

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