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?

  • $\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

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


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