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$ Jan 31, 2014 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, 2014 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, 2014 at 17:20
  • $\begingroup$ I was trying to be unsloppy by avoiding the $=$ sign... $\endgroup$
    – ithisa
    Jan 31, 2014 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, 2014 at 17:27

1 Answer 1


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.