# big and small O notation help

I was hoping someone could help me answer this question. I can't wrap my head around this concept:

Why is $\cal{O}(x^3) = o(x^2)$?

-
Care to accept an answer? – Did Nov 13 '11 at 10:17
Perhaps the OP was confused when someone wrote something like this: ... As $x\to 0$, we have $\sin x = x + O(x^3) = x + o(x^2)$. – GEdgar Nov 13 '11 at 14:18
Doh. That's why you should never mix arithmetics and asymptotics like that (until you and your audience both know what you are doing). – Raphael Nov 13 '11 at 15:26

It isn't. But if $f(x)$ is O$(x^3)$ as $x\to0$, then $|f(x)|\lt C|x^3|$ for some positive constant $C$, so $|f(x)/x^2|\lt C|x|$, so $f(x)/x^2\to0$ as $x\to0$, so $f(x)$ is o$(x^2)$.

-
+1 for adding "as $x \to 0$". – GEdgar Nov 13 '11 at 14:16

Recall that the rigorous meaning of the Bachmann-Landau notation [$f=O(g)$ at $x_0$] is that $f\in O_{x_0}(g)$ where $O_{x_0}(g)$ is the set of functions $h$ such that there exists a finite $C$ and a neighborhood $V$ of $x_0$ such that $g$ and $h$ are defined at least on $V\setminus\{x_0\}$ and $|h(x)|\leqslant C\cdot|g(x)|$ for every $x$ in $V\setminus\{x_0\}$.

Similarly, $o_{x_0}(g)$ is the set of functions $h$ such that there exists a function $k$ and a neighborhood $V$ of $x_0$ such that $g$, $h$ and $k$ are defined at least on $V\setminus\{x_0\}$, $h=kg$ on $V\setminus\{x_0\}$ and $\lim\limits_{x\to x_0}\,k(x)=0$.

Now, let $x_0=0$ and consider the functions $u$ and $v$ defined by $u(x)=x^3$ and $v(x)=x^2$ for every $x$. Then it is true that $O_{x_0}(u)\subseteq o_{x_0}(v)$ in the sense that every function $w$ in $O_{x_0}(u)$ belongs to $o_{x_0}(v)$. But $o_{x_0}(v)\not\subseteq O_{x_0}(u)$ since for example the function $w$ defined by $w(x)=|x|^{5/2}$ is in $o_{x_0}(v)$ but not in $O_{x_0}(u)$.

To sum up, $f=O(g)$ at $x_0$ and $f=o(g)$ at $x_0$, often written as $f(x)=O(g(x))$ at $x_0$ and $f(x)=o(g(x))$ at $x_0$ respectively, are extremely convenient shorthands for $f\in O_{x_0}(g)$ and $f\in o_{x_0}(g)$ respectively, but nothing more.

-

In short, for $x \to \infty$:

$\qquad o(x^2) \subsetneq \cal{O}(x^2) \subsetneq o(x^3) \subsetneq \cal{O}(x^3)$

The inclusions follow directly from definition as does that the first and last are proper. The middle inclusion is proper as witnessed by $x^2\log(x)$. For $x \to 0$, just reverse the inclusions.

-
So: you are doing the case $n \to \infty$, right? When the OP used $x$ as variable, perhaps he wasn't. – GEdgar Nov 13 '11 at 14:16
Oh, right. That never occurred to me. – Raphael Nov 13 '11 at 15:18