1

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

Cameron Buie
  • 102,994
Jonathan Thurgood
  • 13
  • $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. – Daniel Fischer Oct 09 '13 at 18:12

1 Answers1

2

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

Did
  • 279,727
  • 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 – Jonathan Thurgood Oct 09 '13 at 18:35