TOPICS
Search

Little-O Notation


The symbol o(x), pronounced "little-O of x," is one of the Landau symbols and is used to symbolically express the asymptotic behavior of a given function.

In particular, if n is an integer variable which tends to infinity and x is a continuous variable tending to some limit, if phi(n) and phi(x) are positive functions, and if f(n) and f(x) are arbitrary functions, then it is said that f in o(phi) provided that f/phi->0. Thus, phi(n) or phi(x) grows much faster than f(n) or f(x).

Note that little-O notation is the inverse of little-omega notation, i.e., that

 f(n) in o(phi(n)) <==> phi(n) in omega(f(n)).

Additionally, little-O notation is related to big-O notation in that f in o(phi) is stronger than and implies f in O(phi).


See also

Asymptotic, Asymptotic Notation, Big-O Notation, Big-Omega Notation, Big-Theta Notation, Landau Symbols, Little-Omega Notation

This entry contributed by Christopher Stover

Explore with Wolfram|Alpha

References

Hardy, G. H. and Wright, E. M. "Some Notations." §1.6 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 7-8, 1979.

Cite this as:

Stover, Christopher. "Little-O Notation." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/Little-ONotation.html

Subject classifications