Skip to main content
added 292 characters in body
Source Link
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_{n\to\infty}f(n)=g(n)$ says “I don’t care how$\lim$ gives more information; in some ways, it gets there butgives less. In some senses, for large enough $n$$\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 $f$ gets arbitrarily close to $g$$\pm\infty$. If the limit is a real number,” whereas then saying $f(n)=O(g(n))$ says$\lim_{n\to\infty}f(n)=c$ gives more information than $f(n)=O(1)$, “I don’t care how it gets there but there’s a constantwhich suppresses $c$ such that.

On the other hand, for large enough $n$many functions we're interested in, $f$ is$\lim_{n\to\infty}f(n)=\infty$ so $\lim$ gives almost no bigger than $cg$information.” So, really In those cases, big-O suppresses$O$ allows you to give more than limit and the quote is wronginformation.

And don’tI wouldn’t worry about the “suppressing a number” stuff, either. 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. So that’s wrong, tooSomethingl ike $x=O(x^2)$ is even less clear. It's hard to tell what de Bruijn really intended.

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. $\lim_{n\to\infty}f(n)=g(n)$ says “I don’t care how it gets there but, for large enough $n$, $f$ gets arbitrarily close to $g$,” whereas $f(n)=O(g(n))$ says, “I don’t care how it gets there but there’s a constant $c$ such that, for large enough $n$, $f$ is no bigger than $cg$.” So, really, big-O suppresses more than limit and the quote is wrong.

And don’t worry about the “suppressing a number” stuff, either. 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. So that’s wrong, too.

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.

Source Link
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. $\lim_{n\to\infty}f(n)=g(n)$ says “I don’t care how it gets there but, for large enough $n$, $f$ gets arbitrarily close to $g$,” whereas $f(n)=O(g(n))$ says, “I don’t care how it gets there but there’s a constant $c$ such that, for large enough $n$, $f$ is no bigger than $cg$.” So, really, big-O suppresses more than limit and the quote is wrong.

And don’t worry about the “suppressing a number” stuff, either. 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. So that’s wrong, too.