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

share|improve this question
1  
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
add comment

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
+1 for adding "as $x \to 0$". –  GEdgar Nov 13 '11 at 14:16
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

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.