big-O
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000:
The hardware and software on this system was updated September 4th.  Please let me know of any problem you encounter. <caldwell@utm.edu>

Suppose f(x) and g(x) are real valued functions defined for all x greater than some fixed positive real x0. We write

f(x) = O(g(x))     (and we say "f(x) is big-O of g(x)"),
if there is some constant C such that
|f(x)| < C.g(x)
That is, f(x) is O(g(x)) if f is bounded by a constant times g.

For example, 53x2+23x+500 = O(x2), sin(x) = O(1), and any polynomial in x of degree at most n is O(xn).

This big-O notation was introduced by P. Brachmann in 1894.

See Also: LittleOh, SameOrderofMagnitude, AsymptoticallyEqual

References:little-o, same order of magnitude, asymptotically equal


Chris K. Caldwell © 1999-2014 (all rights reserved)