3
$\begingroup$

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?
Improve this question
$\endgroup$
2
  • 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$
    – Yuval Filmus
    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

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.