15-Little-o-notation

Intuitively, the assertion “f(x) is o(g(x))” (read “f(x) is little-o of g(x)”) means that g(x) grows much faster than f(x).

As before, let f be a real or complex valued function and g a real valued function, both defined on some unbounded subset of the positive real numbers, such that g(x) is strictly positive for all large enough values of x.

One writes $f(x)=o(g(x))\text{ as }x\to \infty$ , if for every positive constant ε there exists a constant $x_0$ such that $|f(x)|\le \epsilon g(x)\text{ for all }x\ge x_0.$ ¹

For example, one has $2x=o(x^2)$ and $1/x=o(1),$ both as $x\to \infty .$

The difference between the definition of the big-O notation and the definition of little-o is that ==while the former has to be true for at least one constant M, the latter must hold for every positive constant ε, however small==².

In this way, little-o notation makes a stronger statement than the corresponding big-O notation: ==every function that is little-o of g is also big-O of g, but not every function that is big-O of g is also little-o of g==. For example, $2x^2=O(x^2)$ but $2x^2\ne o(x^2)$.

As g(x) is nonzero, or at least becomes nonzero beyond a certain point, the relation $f(x)=o(g(x))$ is equivalent to $\underset{x\to \infty }{\lim }\frac{f(x)}{g(x)}=0$ (and this is in fact how Landau originally defined the little-o notation).

Little-o respects a number of arithmetic operations. For example,

• if c is a nonzero constant and $f=o(g)$ then $c\cdot f=o(g)$, and
• if $f=o(F)$ and $g=o(G)$ then $f\cdot g=o(F\cdot G).$

It also satisfies a transitivity relation:

• if $f=o(g)$ and $g=o(h)$ then $f=o(h).$

Footnotes

1. Landau, Edmund (1909). Handbuch der Lehre von der Verteilung der Primzahlen [Handbook on the theory of the distribution of the primes] (in German). Leipzig: B. G. Teubner. p. 61. ↩

2. Thomas H. Cormen et al., 2001, Introduction to Algorithms, Second Edition, Ch. 3.1 Archived 2009-01-16 at the Wayback Machine ↩