2
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ It's not a definition. Look at the definition. $\endgroup$ – Raphael Jan 16 '18 at 8:50
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Jan 16 '18 at 8:51
  • $\begingroup$ 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. $\endgroup$ – Umang.B Jan 16 '18 at 8:56
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Umang.B Jan 16 '18 at 10:35
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Jan 16 '18 at 11:08
  • $\begingroup$ Can you refer me a nice book where I can learn Algorithm with lots of Math? $\endgroup$ – Umang.B Jan 16 '18 at 11:10
  • $\begingroup$ Cormen, Rivest, Lieserson and Stein is the usual recommendation. $\endgroup$ – David Richerby Jan 16 '18 at 11:13
  • $\begingroup$ But limit of a function is a number (constant), how it can be a another function? $\endgroup$ – Umang.B Jan 16 '18 at 12:12
1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.