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?
  • 3
    $\begingroup$ 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. $\endgroup$ Commented Mar 10, 2020 at 19:54
  • $\begingroup$ What you can say is that you have $n$ terms, each $O(n)$, thus the sum is $O(n^2)$. $\endgroup$
    – vonbrand
    Commented Mar 11, 2020 at 1:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.