8

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.

Community
  • 1
Mauro Augusto
  • 279
  • 2
    It is a definition - I don't understand what you mean by explanation? You could interpret it as saying $f(0) = 0$ and $f'(0) = 0$. – copper.hat Jan 31 '15 at 06:51
  • Im talking about little o notation? – Mauro Augusto Jan 31 '15 at 07:06
  • 1
    I understand. I don't understand what you are asking. – copper.hat Jan 31 '15 at 07:09
  • I just need an explanation of the grey bit. Like how does o(h) work when h->0 instead of going to infinity – Mauro Augusto Jan 31 '15 at 07:24
  • I don't know what you mean, the definition only involves $h \to 0$? It is exactly equivalent to $f(0) =0$ and $f'(0) = 0$. – copper.hat Jan 31 '15 at 07:28
  • Erm I think you are asking me to explain something I dont get so thats kinda hmmm... but thats an exact quote of the text im reading so im hoping that the people who wrote it know what they are talking about and right now im just lacking an explanation. I dont think you directly substitute h=0 into the limit because h is in the denominator and you cant divide by 0. Its about what goes to 0 faster, some function f(h) or h (the straight line). so like for the limit to hold f(h) would have to be something like x^2 or exp since for x=0.0001 (which is close to 0 ) 0.0001^2/0.0001 is close to 0. – Mauro Augusto Jan 31 '15 at 07:40
  • OP, for intuition compare $\sqrt{h}$ and $h$. The point is not that $\sqrt{h}$, $h^2$ or $h$ is small or as $h \longrightarrow 0$ (they all are). Think about when $h$ is very small (say 0.001) and when $h$ is very big (say 1,000). When $h$ is tiny, $\sqrt{h} >> h$ isn't it? What does that do to your limit? Likewise, when $h$ is big, $\sqrt{h} << h$. Now compare $h^2$ with $h$ in the same way. (the conclusions are opposite now, right?). Do you get the intuition? – Mathemagical Oct 05 '17 at 02:09

2 Answers2

14

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.

hmakholm left over Monica
  • 286,031
-1

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

marwalix
  • 16,773
  • 1
    "$\sqrt{h}$ has slower growth than $h$" is for $h \to \infty$, and not for $h \to 0$ as we have here. – GEdgar Oct 04 '17 at 23:46