I understand that generally if a function $f(h)$ is described as $o(h)$ that $f(h)$ has a smaller rate of growth than $h$ (like it would have to be $\sqrt{h}$). i.e. $\sqrt{h} = o(h)$, just like (for example) $4h=o(h^2)$. The notes I'm reading (CT3), however, states that:
A function $f(h)$ is described as $o(h)$ if:
$$\lim_{h \to 0} \frac{f(h)}{h} = 0 $$
but if I use, for example, $f(h)= \sqrt{h}$ which does have a slower growth rate then $h$ then the limit doesn't go to $0$. Is there a different meaning to little $0$ when its approaching $0$ compared to when it goes to infinity cause the only way that limit holds is if $f(h)$ goes to $0$ faster then $h$ does which I guess means $f(h)$ decreases faster then $h$ as $h \to 0$.
Anyway you can ignore my thoughts on the question but an explanation of the text I quoted would be greatly appreciated.
$\endgroup$ 72 Answers
$\begingroup$Yes, the little-o notation (and Landau symbols in general) behaves differently for $x\to 0$ and for $x\to\infty$.
When we're considering $x\to\infty$ (as you may be familiar with from analysis of algorithms), $\sqrt x$ grows slower than $x$ -- because for large $x$, the square root of $x$ is smaller than $x$ by a ratio that becomes ever more lopsided. Therefore in this context we say that $\sqrt x = o(x)$.
On the other hand, if we're considering $x\to 0$ (which is more common in analysis), then when $x$ is close to zero, $\sqrt x$ is larger than $x$ by a ratio that tends to infinity. Therefore in that context we say that $x = o(\sqrt x)$.
If would be less confusing to make it explicit which limit we're working with, and write something like $$ \sqrt x = \mathop o_{x\to\infty}(x) \qquad\qquad\qquad x = \mathop o_{x\to 0}(\sqrt x) $$ However, in most practical uses of the notation, the limit is the same throughout the entire calculation, so repeating it for every $o$ would be tedious and distracting. So generally it is left implicit, though one should make it clear before one starts using asymptotic notation which limit one is considering.
$\endgroup$ $\begingroup$Your starting point is wrong. $h^2=o(h)$ and not the reverse. $h=o(\sqrt{h})$ and not the reverse.The definition of the Landau notation in the vicinity of a point $x_0$ is $$f=o(g)\Leftrightarrow\lim_{x\to x_0}\frac{f(x)}{g(x)}=0$$
$\endgroup$ 1
