Big-O Notation
The symbol O(x), pronounced "big-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|<Aphi for some constant A and all values n and x.
Note that big-O notation is the inverse of big-omega notation, i.e., that
| f(n) in O(phi(n)) <==> phi(n) in Omega(f(n)). |
Additionally, big-O notation is related to little-O notation in that f in o(phi) is stronger than and implies f in O(phi).
See also
Asymptotic, Asymptotic Notation, Big-Omega Notation, Big-Theta Notation, Landau Symbols, Little-O Notation, Little-Omega NotationThis entry contributed by Christopher Stover
Explore with Wolfram|Alpha
More things to try:
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.Referenced on Wolfram|Alpha
Big-O NotationCite this as:
Stover, Christopher. "Big-O Notation." From MathWorld--A Wolfram Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/Big-ONotation.html