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.


  • 6
    $\begingroup$ 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? $\endgroup$
    – anon
    Dec 15, 2012 at 4:42
  • 5
    $\begingroup$ Note that $\sin (x) = x + \mathcal{O}(x^3)$ is meaningless, you need to add "as $x \rightarrow 0$." $\endgroup$
    – glebovg
    Dec 15, 2012 at 6:12
  • 6
    $\begingroup$ 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$. $\endgroup$ Dec 15, 2012 at 6:19
  • 1
    $\begingroup$ the $\mathcal O(x)$ is for the order (of magnitude) of the error associated with neglecting the rest of the infinite series $\endgroup$ Dec 16, 2012 at 2:26
  • $\begingroup$ @glebovg, isn't the default assumption "as $x\rightarrow\infty$"? (With that $\sin(x) = x + O(x^3)$ is also true.) $\endgroup$
    – Neal Young
    Dec 16, 2012 at 2:31

3 Answers 3


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


$$\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
    $\begingroup$ 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$. $\endgroup$
    – anon
    Dec 15, 2012 at 5:17
  • $\begingroup$ @anon Would you agree with my edit? $\endgroup$
    – glebovg
    Dec 15, 2012 at 5:26
  • 3
    $\begingroup$ $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))$. $\endgroup$
    – anon
    Dec 15, 2012 at 5:46
  • $\begingroup$ I know they are redundant, but I included them because the question is about the "Big Oh". $\endgroup$
    – glebovg
    Dec 15, 2012 at 5:48
  • 1
    $\begingroup$ 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) $\endgroup$
    – Fabian
    Dec 15, 2012 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) $$


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .