1
$\begingroup$

I'm learning about asymptotic analysis and, as a starting point, big and little o definitions.

On the Wikipedia page, http://en.wikipedia.org/wiki/Big_O_notation

further down under the heading for little-$\mathcal{o}$ notation it states

"In this way little-$\mathcal{o}$ notation makes a stronger statement than the corresponding big-$\mathcal{O}$ notation: every function that is little-$\mathcal{o}$ of $g$ is also big-$\mathcal{O}$ of $g$, but not every function that is big-$\mathcal{O}$ g is also little-$\mathcal{o}$ of $g$ (for instance $g$ itself is not, unless it is identically zero near ∞"

This makes sense to me, given the definitions. However, I have an example that seems to be to the contary. In the limit $x\rightarrow0$ the little order of the sin function could be characterized as

$$ \sin(x)=\mathcal{o}(1) $$ i.e., it is always a lot less than 1. According to the arument, this should also be the big-$\mathcal{o}$ of $\sin$ in the same limit. However, in the limit the big $\mathcal{O}$ is

$$ \sin(x)=\mathcal{O}(x) $$

and which as at odds with the relationship between litttle-$\mathcal{o}$ and big-$\mathcal{O}$ in the wiki article.

Where have I went wrong? Is it because saying $\sin(x)=\mathcal{o}(1)$ hasn't characterised the order in terms of a dominant function, but rather picked a constant larger than zero?

Cheers

$\endgroup$
  • $\begingroup$ $o(1)$ is stronger than $\mathcal{O}(1)$. And you will certainly see that $\sin x \in \mathcal{O}(1)$ as $x \to 0$. Whether $o(1)$ is stronger or weaker than $\mathcal{O}(x)$ is a different question. $\endgroup$ – Daniel Fischer Oct 9 '13 at 18:12
2
$\begingroup$

There is no problem since $O(x)\subset o(1)$ hence $\sin x=O(x)$ is more precise than $\sin x=o(1)$. (But recall that $f(x)=O(g(x))$ is only a shorthand for $f\in O(g)$, likewise for $o$.)

$\endgroup$
  • $\begingroup$ Thanks, that makes sense now. I think I got bogged down by the equality (abuse of notation?) leading to thinking it cant be both big O of x and big O 1 at the same time $\endgroup$ – Jonathan Thurgood Oct 9 '13 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.