2
$\begingroup$

In big-O notation, $f(x) = O(g(x))$ as $x\rightarrow \pm\infty$ if

$$\exists C, \delta>0: \forall |x| \geq \delta: |f(x)| < C |g(x)|$$

and, for the case I'm more interested in here, $f(x) = O(g(x))$ as $x\rightarrow 0$ if

$$\exists C, \delta>0: \forall |x| \leq \delta: |f(x)| < C |g(x)|$$

In little-o notation, $f(x) = o(g(x))$ means

$$\lim_{|x|\rightarrow0}\frac{f(x)}{|g(x)|} = 0$$

I've come across big-O before, but this is the first time I've seen little-o. I have experience in applied math, but very little in pure math, and my first reaction (for $x\rightarrow 0$) was "they mean the same thing". Then I thought "but little-o is a more precise upper bound".

What is the relationship between these two notations, and what does the distinction mean practically?

$\endgroup$
  • $\begingroup$ Well, if $f(x)$ is $o(g(x))$ it is also $O(g(x))$ but maybe not the other way around. It is not "more precise", but rather stronger: intuitively, if $f(x)$ is $o(g(x))$ then $g(x)$ grows "much faster" than $f(x)$, whereas $O(g(x))$ implies only that $f(x)$ is eventually bounded above (by some constant multiple of) $g(x)$ -- indeed, the growth rates could be comparable. $\endgroup$ – The_Sympathizer Sep 20 '13 at 11:54
  • $\begingroup$ An example -- though note here I'm using the O-notation for growth near infinity, not near 0: If $f(x) = x$ and $g(x) = x^2$, then $f(x)$ is $o(g(x))$ AND $O(g(x))$, but if $f(x) = x^2$ then $f(x)$ is only $O(g(x))$ and NOT $o(g(x))$. $\endgroup$ – The_Sympathizer Sep 20 '13 at 11:56
  • $\begingroup$ An example for near 0: $f(x) = \frac{1}{x}$ and $g(x) = \frac{1}{x^2}$. Then $f(x)$ is $o(g(x))$ (as $x \rightarrow 0$) while if $f(x) = \frac{1}{x^2}$ then $f(x)$ is only $O(g(x))$ and not $o(g(x))$. $\endgroup$ – The_Sympathizer Sep 20 '13 at 11:58
4
$\begingroup$

In the briefest possible terms, $f \in O(g)$ is like saying $f \leqslant g$ asymptotically, and $f \in o(g)$ is like saying $f < g$ asymptotically.

As an example, if $f(x) = x$ and $g(x) = 2x$,we have that that $f \in O(g)$, but $f \notin o(g)$ and $g \notin o(f)$. If $f(x) = x^2$ and $g(x) = x$, then $f \in o(g)$ and $f \in O(g)$.

As an aside, be very aware of context. In various probabilistic situations, we define $O$-notation with a limit as $x\rightarrow 0$. In most algorithmic applications, we take limits as $x \rightarrow \infty$. Always make sure it's clear what you're working with before using either notation. $O$-notation is probably the most abused thing in all of mathematics.

$\endgroup$
  • 1
    $\begingroup$ Also note: Notation $f \in O(g)$ is quite rare, compared to notation $f = O(g)$. $\endgroup$ – GEdgar Sep 20 '13 at 13:42
  • $\begingroup$ Indeed. I didn't want to start listing abuses of $O$ notation because I don't think I'd ever stop. It's more common to say things like $2x = O(x)$. $\endgroup$ – ymbirtt Sep 20 '13 at 14:13
  • $\begingroup$ $x^2$ is not in $O(x)$, at least when $x \to \infty$. Typo? $\endgroup$ – ftfish Sep 20 '13 at 14:44
  • $\begingroup$ From OP's definitions, we're sending $x \rightarrow 0$, so I'm remaining consistent with that. $\endgroup$ – ymbirtt Sep 20 '13 at 15:08
  • $\begingroup$ @GEdgar thanks, discussion of this helps me to get to grips with it. I've always been a little bit uncomfortable with the use of $=$, and thinking about it in terms of sets is more consistent. $\endgroup$ – TooTone Sep 21 '13 at 9:07
3
$\begingroup$

Little $o$ means lim sup of absolute value $=0$, big $O$ means lim sup of absolute value $< \infty$.

$\endgroup$
  • $\begingroup$ Thanks, but I thought big O could be used for $\rightarrow 0$ as well as $\rightarrow \infty$? The former was what I was more interested in because it then has a similar meaning to little o. (My post was a little ambiguous and I see you changed $<$ in my post to $\ge$ -- I've changed that back and added some more which hopefully makes it clearer.) $\endgroup$ – TooTone Sep 20 '13 at 14:31
  • $\begingroup$ You are referring to my correction? Okay, I am sorry then the same remains true. It should be indicated though wether you look at the behaviour at $0$ or at $\infty$. A continuous variable transformation, e.g. $x \mapsto x^{-1}$ exchanges between the setting and my statement remains valid;) $\endgroup$ – Marc Palm Sep 20 '13 at 14:39
  • $\begingroup$ Yes you're right I should have indicated whether I was looking at limit towards zero or infinity. I can see how a reciprocal transformation might make the situations equivalent; however I still don't quite understand your answer. $\endgroup$ – TooTone Sep 20 '13 at 19:52
  • $\begingroup$ my answer remains valid no matter to where the limit goes. $\endgroup$ – Marc Palm Sep 21 '13 at 14:57
  • $\begingroup$ I think what I don't understand is, in simple terms, your use of "sup" means. $\endgroup$ – TooTone Sep 21 '13 at 18:01
1
$\begingroup$

check this out :

http://en.wikipedia.org/wiki/Big_O_notation

:-) it's not just Big O notation in the page

$\endgroup$
1
$\begingroup$

Looking at how $O(1)$ and $o(1)$ are sufficient to understand the general case.

Suppose $f \in O(1)$. Then

$$ \lim_{x \to +\infty} f(x) < +\infty$$

if the limit exists. Or more generally, if the limit does not exist, then

$$\sup_{x \to +\infty} f(x) < +\infty$$

Now suppose $f \in o(1)$. Then

$$\lim_{x \to \infty} f(x) = 0 $$

$\endgroup$

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.