Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
5  
Intuitively, it means that $O(x^3)$ is a placeholder for some function that is $\le Cx^3$ eventually (i.e. for all $x$ beyond a certain point) for some value $C$. Is there anything in particular about the Wikipedia article on Big O notation that you'd like to see elaborated upon or clarified? – anon Dec 15 '12 at 4:42
4  
Note that $\sin (x) = x + \mathcal{O}(x^3)$ is meaningless, you need to add "as $x \rightarrow 0$." – glebovg Dec 15 '12 at 6:12
6  
It means informally that when $x$ is close enough to $0$, then $\sin x$ is about $x$, with an error less than a constant times $|x^3|$. Note that if $x$ is say $1/100$, then $x^3$ is $1/1000000$, tiny compared to $1/100$. – André Nicolas Dec 15 '12 at 6:19
1  
the $\mathcal O(x)$ is for the order (of magnitude) of the error associated with neglecting the rest of the infinite series – Elements in Space Dec 16 '12 at 2:26
    
@glebovg, isn't the default assumption "as $x\rightarrow\infty$"? (With that $\sin(x) = x + O(x^3)$ is also true.) – Neal Young Dec 16 '12 at 2:31
up vote 6 down vote accepted

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.

share|cite|improve this answer
1  
The equivalence you have is incorrect. $f=O(g)$ is much more general than $f\sim g$, and it is the latter that means $\lim(f/g)=1$. – anon Dec 15 '12 at 5:17
    
@anon Would you agree with my edit? – glebovg Dec 15 '12 at 5:26
3  
$f\in \Theta(g)$ does not even imply $\lim(f/g)$ exists. Also, the three conditions $f\in O(g)$, $f\in\Theta(g)$ and $f\in\Omega(g)$ together are redundant because $f\in\Theta(g)\iff (f\in O(g)\wedge f\in \Omega(g))$. – anon Dec 15 '12 at 5:46
    
I know they are redundant, but I included them because the question is about the "Big Oh". – glebovg Dec 15 '12 at 5:48
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) – Fabian Dec 15 '12 at 6:33

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) $$

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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