Skip to main content
2 of 2
added 292 characters in body
David Richerby
  • 82.2k
  • 26
  • 144
  • 238

It’s trying to give an intuition and nothing more so, if the passage is not helpful to you, just skip it. Look at the actual definition instead.

Honestly, I think it’s a very bad and unhelpful attempt at giving intuition. In some ways, $\lim$ gives more information; in some ways, it gives less. In some senses, $\lim$ is more specific in that it gives a single value that the function asymptotically approaches, and the notion of limit makes sense approaching points other than $\pm\infty$. If the limit is a real number, then saying $\lim_{n\to\infty}f(n)=c$ gives more information than $f(n)=O(1)$, which suppresses $c$.

On the other hand, for many functions we're interested in, $\lim_{n\to\infty}f(n)=\infty$ so $\lim$ gives almost no information. In those cases, big-$O$ allows you to give more information.

I wouldn’t worry about the “suppressing a number” stuff. Saying $3x=O(x)$ suppresses the number three but $3x+1=O(x)$ suppresses two numbers, $3x=O(3x)$ suppresses nothing and $x=O(3x+1)$, er, un-suppresses stuff. Somethingl ike $x=O(x^2)$ is even less clear. It's hard to tell what de Bruijn really intended.

David Richerby
  • 82.2k
  • 26
  • 144
  • 238