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$ 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
    Mar 11, 2020 at 1:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.