# Induction pitfalls with O notation and recursion

I read the following in CLRS 3rd Ed:

I'm not sure I understand exactly how to avoid this pitfall.

1. How would one know that the $$\mathcal{O}$$ notation in this case grows with $$n$$ and is thus not constant?
2. What's a good way to systematically avoid this type of pitfall?
• There is no good answer for this. The notation is ambiguous. When proving $f(n) = O(n)$ by induction, it's best to instead prove $f(n) \leq Cn$, which would avoid such problems. Mar 10, 2020 at 19:54
• What you can say is that you have $n$ terms, each $O(n)$, thus the sum is $O(n^2)$. Mar 11, 2020 at 1:22