Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
3  
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

2 Answers 2

up vote 2 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|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|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.