In mathematical analysis, and in particular in the analysis of algorithms, to classify the growth of functions one has recourse to asymptotic notations. Knuth advocated the following notations (other notations hold in various contexts, e.g., Landau and Hardy notation):

• O-notation (big-oh)
• o-notation (little-oh)
• Ω-notation
• ω-notation
• Θ-notation

The minute details of a function for arbitrary big values of its argument seldom matter. Often it is enough to compare its overall behaviour to standard sets of mathematical function so as qualify the function at hand along a restricted set of significant behaviours, such as bounded, oscillating, divergent, etc..., and to indicate the speed with which it reach this asymptotic behaviour.

For instance if a function tends to zero faster than a square integrable function, it is known that it has a well-defined Fourier transform, no matter what the function actually looks like.

The notation is an equality between the function at hand, and the known function it behaves like or is compared to in the asymptotic limit. For example, $g(x)=\backslash Theta\; (x^2)$ means that the function $g(x)$ behaves asymptotically like the function $x^2$ (see below for the meaning of each notation).

The notation is highly conventional and must not be assigned any mathematical significance. For example, if $g=\backslash Theta(f)$ and $h=\backslash Theta(f)$ it does not mean that $g=h$. A better notation would be $g\; \backslash in\; \backslash Theta\; (f)$ as $\backslash Theta(f)$ (and others) can be regarded as the set of functions sharing a common asymptotic behavior.

Definitions

(In all that follows, the asymptotic relations are considered with respect to x→+∞. Often another limit point is of interest (e.g. x→0 or x→a∈R). Then of course the definitions below must be modified adequately. To avoid misunderstandings, the limit point should be made precise, e.g. by writing (a) below the "=" sign or (x→a) behind the equation, as in $x\backslash begin\{matrix\}=\backslash \backslash *\{\}\_\{(\backslash infty)\}\backslash end\{matrix\}o(x^2)~;~x^2=o(x)~~(x\backslash to0)$.)

The O-notation means that the function is bounded from above (also known as dominated) by a function which varies like $f$, i.e.,

$g=O(f)\backslash iff\; g\backslash in\; O(f)\backslash iff(\backslash exists\backslash alpha>0)(\backslash exists\; x\_0)(\backslash forall\; x>x\_0)~|g(x)|\backslash le\backslash alpha|f(x)|.$

Thus, $f=O(1)$ means that $f$ is bounded and $f=O(x)$ means that $f$ does not grow faster than linear. It corresponds for functions in asymptotic limit to the relation $\backslash le$ between numbers.

The o-notation restricts the O-notation to mean that the function is bounded from above but that the bound must not be tight, i.e., the function must grow strictly slower than its o-reference. Formally:

so that for instance $2x^n=O(x^n)\backslash ,$ but is not $o(x^n)\backslash ,$. (This relation is also pronounced g is negligible w.r.t. f.) Also, $x^n=o(x^m)\backslash ,$ if O if $n\backslash le\; m$. It corresponds for functions in asymptotic limit to the relation < between numbers.

The Ω-notation is the counterpart of O-notation for functions bounded from below:

$g=\backslash Omega(f)\backslash iff\; g\backslash in\backslash Omega(f)\backslash iff(\backslash exists\backslash alpha>0)(\backslash exists\; x\_0)(\backslash forall\; x>x\_0)~\backslash alpha|f(x)|\backslash le|g(x)|.$

Likewise ω-notation is the counterpart of o-notation for functions bounded from below without converging towards their reference:

Finally, Θ-notation means there is an asymptotically tight-bound, i.e., that the function really behaves like its reference function:

$g=\backslash Theta(f)\backslash iff\; g\backslash in\backslash Theta(f)\backslash iff(\backslash exists\backslash alpha>0)(\backslash exists\backslash beta>0)(\backslash exists\; x\_0)(\backslash forall\; x>x\_0)~\backslash alpha\; f(x)\backslash le\; g(x)\backslash le\backslash beta\; f(x).$

The function can sandwiched by two representatives of its Θ-reference. For instance $x^2+x=\backslash Theta(x^2)$. This means that for high enough values of $x$, the function $x^2\; +\; x$ behaves like $x^2$ only and its linear part has become irrelevant or negligible. It corresponds for functions in asymptotic limit to the relation $=$ between numbers.

Note that the "=" sign used in the definition above does not mean equality. Although the use of "∈" is more logical and becomes frequent especially in computer science, the use of "=" is still the most current and well-established notation found in the literature.

In layman's terms, one would say that

• $f\backslash in\; O(g)$ means that f has order at most g.
• $f\backslash in\; \backslash Omega(g)$ means that f has order at least g.
• $f\backslash in\; \backslash Theta(g)$ means that f has order g.

Properties

• All of the above are transitive relations:

If $f\backslash in\; O(g)$ and $g\backslash in\; O(h)$, then $f\backslash in\; O(h)$, and the same holds for o, ω, Ω and Θ.

• Θ is the equivalence relation associated to the preorder O, thus

$f\backslash in\backslash Theta(g)\backslash iff\; g\backslash in\backslash Theta(f)$.

The following implications hold:

• If $f\backslash in\; o(g)$, then $f\backslash in\; O(g)$.
• If $f\backslash in\; O(g)$, then $g\backslash in\backslash Omega(f)$.

These notations are widely used in algorithmics to estimate the complexity of an algorithm. Sometimes, in mathematics, the O-notation is used with the meaning of the Θ-notation.

To simulate the meaning, the following allegory can be used

• $f\backslash in\; O(g)$ is similar to $f\backslash le\; g$.
• $f\backslash in\backslash Omega(g)$ is similar to $f\backslash ge\; g$.
• $f\backslash in\backslash Theta(g)$ is similar to $f=g\backslash ,$.
• $f\backslash in\; o(g)$ is similar to
• $f\backslash in\backslash omega(g)$ is similar to $f>g\backslash ,$.

See also

• Asymptotic expansion: approximation of functions generalizing Taylor's formula.
• Nachbin's theorem: a precise way of bounding complex analytic functions so that the domain of convergence of integral transforms can be stated.

References

^* D. E. Knuth. Fundamental Algorithms, vol. 1 of The Art of Computer Programming.

mathematical notation | asymptotic analysis