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$
3
  • $\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$ Sep 20, 2013 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$ Sep 20, 2013 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$ Sep 20, 2013 at 11:58

4 Answers 4

6
$\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$
5
  • 2
    $\begingroup$ Also note: Notation $f \in O(g)$ is quite rare, compared to notation $f = O(g)$. $\endgroup$
    – GEdgar
    Sep 20, 2013 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, 2013 at 14:13
  • $\begingroup$ $x^2$ is not in $O(x)$, at least when $x \to \infty$. Typo? $\endgroup$
    – ftfish
    Sep 20, 2013 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, 2013 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, 2013 at 9:07
4
$\begingroup$

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

$\endgroup$
6
  • $\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, 2013 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, 2013 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, 2013 at 19:52
  • $\begingroup$ my answer remains valid no matter to where the limit goes. $\endgroup$
    – Marc Palm
    Sep 21, 2013 at 14:57
  • $\begingroup$ I think what I don't understand is, in simple terms, your use of "sup" means. $\endgroup$
    – TooTone
    Sep 21, 2013 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$
0

You must log in to answer this question.

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