# What $O$ -symbol supresses?

I am reading this book Asymptotic Methods in Analysis by N. G. de Bruijn. It describes the definition of $O$ symbol as

A weaker form of suppression of information is given by the Bachmann-Landau O-notation. It does not suppress a function, but only a number. That is to say, it replaces the knowledge of a number with certain properties by the knowledge that such a number exists. The O-notation suppresses much less information than the limit notation, and yet it is easy enough to handle. Assume that we have the following explicit information

I don't under what does this means...

...That is to say, it replaces the knowledge of a
number with certain properties by the knowledge that such a
number exists...


Can anyone throw light on this passage of definition? It will be a great help. Thanks in Advance!

• It's not a definition. Look at the definition. – Raphael Jan 16 '18 at 8:50
• Arguably, this passage is wrong, at least if de Bruijn uses the common definition of O. There is a limit process involved, and more than a single number is suppressed. – Raphael Jan 16 '18 at 8:51
• Oh! I guess he is giving vague idea about O-Symbol. I don't know should I ask you more?? Book on page 3 he talks about that. – Umang.B Jan 16 '18 at 8:56

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.

• But check this out reference under see reference section. I guess, this guy's book is famous or something. de Bruijn, N. G. Asymptotic Methods in Analysis. New York: Dover, pp. 3-10, 1981. – Umang.B Jan 16 '18 at 10:35
• Yeah, maybe there's some context that makes de Bruijn's comments more sensible but, in isolation, they're very disappointing from such a major figure in mathematics. – David Richerby Jan 16 '18 at 11:08
• Can you refer me a nice book where I can learn Algorithm with lots of Math? – Umang.B Jan 16 '18 at 11:10
• Cormen, Rivest, Lieserson and Stein is the usual recommendation. – David Richerby Jan 16 '18 at 11:13
• But limit of a function is a number (constant), how it can be a another function? – Umang.B Jan 16 '18 at 12:12

Let's look at the expression $E=x+x^2+x^3+\cdots$, having in mind that $x\rightarrow 0$.Then this number can be written as $x(1+x+x^2+x^3+\cdots)$. So, $E$ has the property that it is a product of $x$ and $(1+x+x^2+x^3+\cdots)$ where the latter is bounded by some constant $C$ for all $x$ small enough. Also, $E= O(x)$, in other words it informs us of the existence of a constant $\tilde{C}$ such that $E\leq \tilde{C}x$ without telling what this constant is.

So, whenever we don't care about the exact value of $\tilde{C}$, then the big $O$ notation gives a more compact, easier to work with, expression.

Example: \begin{align*} \lim_{x\rightarrow 0} \frac{\cos(x)-1+\frac{x^2}{2}}{x^4}&=\lim_{x\rightarrow 0} \frac{\sum_{n\geq 0}(-1)^n\frac{x^{2n}}{(2n)!}-1+\frac{x^2}{2}}{x^4}\\ &=\lim_{x\rightarrow 0} \frac{(1-\frac{x^2}{2}+\frac{x^4}{4!}+O(x^6))-1+\frac{x^2}{2}}{x^4}\\ &=\lim_{x\rightarrow 0} \frac{\frac{x^4}{4!}+O(x^6)}{x^4}\\ &=\lim_{x\rightarrow 0} \frac{1}{4!}+O(x^2)\\ &=\frac{1}{4!} \end{align*} The big $O$ notation supresses knowledge in the sense what whenever you have an expression $E$, then $E=O(E)$ is always correct. In other words the big $O$ of $E$ is always possible to be represented by at most the same amount of terms.

It also supresses less information than the limit in the sense that any limit$=c$ can be rewritten as $c+O(a_n)$ where $a_n\rightarrow 0$. In other words, the big O notation can not only tell you what the limit is, but also how fast you converge there.