The Prime Glossary: big-O

big-O
(another Prime Pages' Glossary entries)

Glossary:

Prime Pages:

Top 5000:

Suppose f(x) and g(x) are real valued functions defined for all x greater than some fixed positive real x₀. 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, 53x²+23x+500 = O(x²), sin(x) = O(1), and any polynomial in x of degree at most n is O(xⁿ).

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