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

14
$\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$
2
  • 1
    $\begingroup$ This is confusing to me. Basically we are using equal notation for two almost opposite behaviour. $\endgroup$ Sep 27, 2022 at 21:28
  • $\begingroup$ I agree to @Curiousstudent. How can this be true, and never mentioned anywhere? I checked Wikipedia, MathWorld, a number of online lecture notes ... Is this supposed to be obvious? Very strange ... :) $\endgroup$ May 11 at 14:58
-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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .