This question already has an answer here:
- Error in the use of asymptotic notation 3 answers
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?