# Big-O Interpretation

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.

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

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.

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