Wikipedia: Big O

Big O notation (with a capital letter O, not a zero), also called Landau's symbol, is a symbolism used in complexity theory, computer science and mathematics to describe the asymptotical behavior of functions. Basically, it tells you how fast a function grows or declines.

For example, when analyzing some algorithm, one might find that the time it takes to complete a problem of size n is given by T(n) = 4 n² - 2 n + 2. If we ignore constants (which makes sense because those depend on the particular hardware the program is run on) and slower growing terms, we could say "T(n) grows at the order of n²" and write:T(n) = O(n²). The letter "O" comes from the word "order".

In mathematics, it is often important to get a handle on the error term of an approximation. For instance, people will write

: e^x = 1 + x + x² / 2 + O(x³) for x -> 0

to express the fact that the error is smaller in absolute value than some constant times x³ if x is close enough to 0.

For the formal definition, suppose f(x) and g(x) are two functions defined on some subset of the real numbers. We write

: f(x) = O(g(x))

(or f(x) = O(g(x)) for x -> ∞ to be more precise) if and only if there exist constants N and C such that

: |f(x)| ≤ C |g(x)| for all x>N.

Intuitively, this means that f does not grow faster than g.

If a is some real number, we write

: f(x) = O(g(x)) for x -> a

if and only if there exist constants d and C such that

: |f(x)| ≤ C |g(x)| for all x with |x-a| < d.

The first definition is the only one used in computer science (where typically only positive functions with a natural number n as argument are considered; the absolute values can then be ignored), while both usages appear in mathematics.

Here is a list of classes of functions that are commonly encountered when analyzing algorithms. The slower growing functions are listed first. c is some arbitrary constant.

notation		name
O(1)		constant
O(log(n))		logarithmic
O((log(n))^c)		polylogarithmic
O(n)		linear
O(n²)		quadratic
O(n^c)		polynomial
O(cⁿ)		exponential

Note that O(n^c) and O(cⁿ) are very different. The latter grows much faster, no matter how big the constant c is. Note, too, that O(log n) is exactly the same as O(log(n^c)). The logarithms differ only by a constant factor, and the big O notation ignores that. Similarly, logs with different constant bases are equivalent.

The above list is useful because of the following fact: if a function f(n) is a sum of functions, one of which grows faster than the others, then the faster growing one determines the order of f(n). Example: If f(n) = 10 log(n) + 5 (log(n))³ + 7 n + 3 n² + 6 n³, then f(n) = O(n³). One caveat here: the number of summands has to be constant and may not depend on n.

This notation can also be used with multiple variables and with other expressions on the right side of the equal sign. The notation:

: f(n,m) = n² + m³ + O(n+m)

represents the statement:

: ∃C ∃N ∀n,m>N : f(n,m)≤n²+m³+C(n+m)

Obviously, this notation is abusing the equality symbol, since it violates the axiom of equality: "things equal to the same thing are equal to each other". To be more formally correct, some people (mostly mathematicians, as opposed to computer scientists) prefer to define O(g(x)) as a set-valued function, whose value is all functions that do not grow faster then g(x), and use set membership notation to indicate that a specific function is a member of the set thus defined. Both forms are in common use, but the sloppier equality notation is more common at present.

Another point of sloppiness is that the parameter whose asymptotic behaviour is being examined is not clear. A statement such as f(x,y) = O(g(x,y)) requires some additional explanation to make clear what is meant. Still, this problem is rare in practice.

In addition to the big O notations, another Landau symbol is used in mathematics: the little o. Informally, f(x) = o(g(x)) means that f grows much slower than g and is insignificant in comparison.

Formally, we write f(x) = o(g(x)) (for x -> ∞) if and only if for every C>0 there exist N such that

: |f(x)| ≤ C |g(x)| for all x>N.

Also, if a is some real number, we write f(x) = o(g(x)) for x -> a if and only if for every C>0 there exist d such that

: |f(x)| ≤ C |g(x)| for all x with |x - a| < d.

Big O is the most commonly-used of five notations for comparing functions:

Notation	Definition	Analogy
f(n) = O(g(n))	see above	≤
f(n) = o(g(n))	see above	<
f(n) = Ω(g(n))	g(n)=O(f(n))	≥
f(n) = ω(g(n))	g(n)=o(f(n))	>
f(n) = θ(g(n))	f(n)=O(g(n)) and g(n)=O(f(n))	=

The notations θ and Ω are often used in computer science; the lowercase o is common in mathematics but rare in computer science. The lowercase ω is rarely used.

A common error is to confuse these by using O when θ is meant. For example, one might say "heapsort is O(n log n)" when the intended meaning was "heapsort is θ(n log n)". Both statements are true, but the latter is a stronger claim.