2
$\begingroup$

In the wikipedia article about the Big-O notation (or the Landau-notation) I came across the notation $f(x) < o(g)$ and $f(x) > o(g(x)$, but what should that mean?

I know that $f(x) = o(g(x))$ means $$ \lim_{x \to \infty} \frac{f(x)}{g(x)} = 0. $$ or equivalently $\forall \varepsilon > 0 \exists N \forall x > N : |f(x)| \le \varepsilon |g(x)|$ (guess on wikipedia the $|\cdot |$-sign around $g(x)$ where forgotten, otherwise it is not equivalent to the limit definition). But I am a little bit puzzled, according to the text $f(x) < o(g(x))$ is the negation of $$ \limsup_{x\to \infty} \frac{f(x)}{g(x)} > 0. $$ Hence equivalent to $\limsup_{x\to \infty} \frac{f(x)}{g(x)} \le 0$, meaning there is some value $C \le 0$ such that the quotient gets infinitely often arbitrary close to it, and this holds for no positive value (i.e. $C$ is the largest limit point).

i) If this value is $-\infty$, then this would give $\lim |f(x)/g(x)| = \infty$, hence $f = \omega(g)$, which gives $g = o(f)$.

ii) If this value is some real number $C < 0$, then $$ \limsup_{x\to\infty} \frac{-f(x)}{g(x)} < \infty $$ which implies $f \in O(g)$ as $|f(x)| \le C |g(x)|$ for some $C$ and sufficiently large $x$, or if there is no smallest limit point present that $|f(x)| \le C|g(x)|$ holds infinitely often.

iii) If this value is zero, then infinitely often $g(x)$ would dominate $f(x)$, giving something similar to $f = o(g)$.

Maybe I have understood something wrong in my analysis, but if this is equivalent to my cases than this symbol would not make any sense to me [for example case i) gives $g = o(f)$], but intuitively I would read $f < o(g)$ as something like "$f$ is smaller than a function that is dominated by $g$, but this would also not make that much sense as $f = o(g)$ and $g = o(h)$ imply $f = o(g)$, so this could be said with the $o$-symbol.

So what is the meaning behind these symbols, what do they say about the relations of both functions? And why would someone use them?

$\endgroup$
2
  • 3
    $\begingroup$ I've never seen f>o(g) in any context. $\endgroup$ Mar 31, 2018 at 0:01
  • 2
    $\begingroup$ Same. I would bet on a badly written section of a Wikipedia article rather than on a cryptic but well-spread notation. $\endgroup$
    – Clement C.
    Mar 31, 2018 at 0:03

1 Answer 1

3
$\begingroup$

My interpretation: this is not a notation anybody seems to be using, and I take it as the result of a sloppily written part of a Wikipedia article.

In more detail: This is the very first time I ever see these notations $<o(\cdot)$ and $> o(\cdot)$ (I do research in theoretical computer science); they are not even defined in the very Wikipedia article which uses them once; and I hope never to see them again, as they are at best confusing, at worst nonsensical (with regard to how $o(\cdot)$ is defined).


Now, to try and assign a meaning to them based on this part of the Wikipedia article which uses them without defining them, let's look at $f < o(g)$ (at $+\infty$). It is stated that "$f(x) = \Omega_R(g(x))$ is the negation of $f(x) < o(g(x))$", so going backwards, based on the definition of the former as $$ \limsup_{x\to\infty} \frac{f(x)}{g(x)} > 0 $$ the negation corresponding to $f(x) < o(g(x))$ would be something like $$\forall C>0 \exists A\, \forall x> A,\ f(x) < Cg(x)$$ if I did not get the quantifiers wrong. Again, I see absolutely no point in using this notation $f(x) < o(g(x))$, since it's not only confusing, but by very definition would be equivalent to the much more understandable $f(x) \neq \Omega_R(g(x))$.


PS: note that all that is in the Hardy–Littlewood sense: it is basically never used in computer science, for which $\Omega(\cdot)$ takes a different meaning to begin with. (I am writing this as you included the {computer-science} tag in your question)

$\endgroup$
4
  • $\begingroup$ Ok. Thanks for your answer, may I ask, is my analysis by the three cases correct? (for then it could mean anything from three totally different things....) $\endgroup$
    – StefanH
    Mar 31, 2018 at 19:59
  • $\begingroup$ @StefanH eyeballing (ii), I'd say there is a mistake there. Multiplying a limsup by -1 leads to a liminf. $\endgroup$
    – Clement C.
    Mar 31, 2018 at 20:01
  • $\begingroup$ Yes, thank you. But $\liminf -f(x)/g(x) < \infty$ is not much of a strong statement, as far as I can see it only excluded the case $\lim -f(x)/g(x) = \infty$, which gives the same as i). Anyway, giving this some meaning gives me some hard time, but as you said maybe this is a fruitless attempt... $\endgroup$
    – StefanH
    Mar 31, 2018 at 20:19
  • 1
    $\begingroup$ @StefanH That's true (I did not claim it would make a big difference, just that the case (ii) was currently incorrect). As for (iii), the domination "infinitely often" is not the same as what the $o(\cdot)$ would yield (with is more like "domination except for finitely many terms"). $\endgroup$
    – Clement C.
    Mar 31, 2018 at 20:30

You must log in to answer this question.

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