13
$\begingroup$

I have trouble understanding what the "Big O" notation, or asymptotic notation means. For instance, if you have $\sin(x)=x+O(x^3)$, what does this mean? Can anyone describe it in a simple way? I tried looking it up but it the explanations didn't help much.

Thanks.

  • 0
    @glebovg, Both are true. If $f(x) = o(g(x))$, then $f(x) = O(g(x))$ as well. For example, $x^2 = O(x^2)$ and $x^2 = O(x^3)$ and $x^2 = o(x^3)$ are all true (as $x\rightarrow \infty$).2012-12-16

3 Answers 3

8

Note: We usually abuse the notation and write $f(x) = \mathcal{O}(g(x))$ instead of $f(x) \in \mathcal{O}(g(x))$. However, $g(x) \not = \mathcal{O}(f(x))$ in general, because $g(x) \notin \mathcal{O}(f(x))$ in general.

If $f(x) \in \mathcal{O}(g(x))$ then for large $x$, $f(x)$ has the same rate of growth as $g(x)$ or $f(x)$ has a smaller rate of growth than $g(x)$. When we write

$\sin(x) = x + \mathcal{O}(x^3) \text{ as $x \rightarrow 0$}$

we mean $\sin(x)$ is equal to $x$ plus some quantity that is "Big Oh of $x^3$." The last quantity is not stated exactly, but "Big Oh" tells us that the absolute value of the last quantity is no more than a positive constant times $x^3$. We can even write many familiar results from calculus such as $\sin(x) \leq 1$ and $n! \sim {(2\pi)^{1/2}}{n^{1/2}}{n^n}{e^{-n}}$ (Stirling's approximation) using the Big Oh:

$\sin(x) = \mathcal{O}(1) \text{ as $x \rightarrow 0$}$ $n! = \mathcal{O}({n^{1/2}}{n^n}{e^{-n}}) \text{ as $x \rightarrow +\infty$}.$

Another familiar result

$\mathop{\lim}\limits_{x \to 0}\frac{{\sin(x)}}{x} = 1$

can be written as

$\sin(x) = \mathcal{O}(x) \text{ as $x \rightarrow 0$}$

but since the limit is $1$, we can actually write $\sin(x) \sim x \text{ as $x \rightarrow 0$}$.

You can think of "Big Oh" as $\mathop{\lim \sup}\limits_{x \to \infty} \left|\frac{{f(x)}}{{g(x)}}\right| = K \in \mathbb{R^+} \Rightarrow f(x) \in \mathcal{O}(g(x)).$

Technically:

$\mathop{\lim \sup}\limits_{x \to \infty} \left|\frac{{f(x)}}{{g(x)}}\right| = K \in \mathbb{R^+} \Rightarrow f(x) \in \mathcal{O}(g(x)) \wedge f(x) \in \Theta(g(x)) \wedge f(x) \in \Omega(g(x))$

where $\Theta$ and $\Omega$ are related asymptotic notations.

See Concrete Mathematics by Graham, Knuth, and Patashnik for a good introduction to asymptotics.

  • 1
    how about replacing $\lim$ by $\limsup$ to answer @anon's remark? (and maybe also introducing absolute values to handle functions which have not a given fixed sign)2012-12-15
3

On of the main reasons to use big-Oh/asymptotic/Landau notation is to understand how some complicated function works by expanding it in easier functions, taking the argument to $\infty$ (or wherever you want) and looking at the largest terms on RHS. In you case the idea is that as $x \to 0$, $\sin x =O(x)$ by expanding in Maclaurin series. Another interesting example I'll show here is Harmonic sum:

$ H(n)=\sum_{k=1}^{n} \frac{1}{k} = O( \log n) $

3

First, the Big O (and its cousins: little o, Big and little theta, etc) notation is a mathematical device used for asymptotic quantification of the growth rate of a function near a point, often 0 or infinity. If you don't specify which point, infinity is assumed. That is why in your $sin x$ example, you should have added that x approaches 0.

As for why $sin(x)=x+O(x^3)$ as x approaches 0, it comes from the Taylor expansion of the $sin$, which is of course an infinite series. The O notation simply gives you the "bottom line". Specifically, it says that $sin x$ near 0 is equal to the argument $x$ itself plus a quantity whose vanishing (not growth) rate (not value, realize) as $x$ approaches 0 is no slower than the vanishing rate of $x^3$.

Finally, it is pathetic that the manipulation of the Big O notation is plagued with huge abuse. To imagine the size of the abuse, recall that the O denotes a set, not a quantity nor even a function. As such it should not be equaled to a function, as in $7n^2+5=O(n^3)$. Nor should it be added to a variable as in your example $sin(x)=x+O(x^3)$, or even to itself as in what is sometimes called "Big O algebra". But this abuse has accumulated over the years anyway and it is hard to change it now.