8
$\begingroup$

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$
7
  • 2
    $\begingroup$ 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$. $\endgroup$
    – copper.hat
    Jan 31, 2015 at 6:51
  • $\begingroup$ Im talking about little o notation? $\endgroup$ Jan 31, 2015 at 7:06
  • 1
    $\begingroup$ I understand. I don't understand what you are asking. $\endgroup$
    – copper.hat
    Jan 31, 2015 at 7:09
  • $\begingroup$ I just need an explanation of the grey bit. Like how does o(h) work when h->0 instead of going to infinity $\endgroup$ Jan 31, 2015 at 7:24
  • $\begingroup$ 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$. $\endgroup$
    – copper.hat
    Jan 31, 2015 at 7:28

2 Answers 2

13
$\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$
-1
$\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
  • 1
    $\begingroup$ "$\sqrt{h}$ has slower growth than $h$" is for $h \to \infty$, and not for $h \to 0$ as we have here. $\endgroup$
    – GEdgar
    Oct 4, 2017 at 23:46

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.