Big O Notation

The big O notation is used to describe the asymptotic efficiency of algorithms. It is written O(f(n)) where n∈N (sometimes sets other than the set of natural numbers, N, are used).

The expression O(f(n)) is the set of functions {g(n):∃c,n0∈N, ∀n≥n0, 0≤g(n)≤cf(n)}. In plain English, this set is populated by functions that are bounded cf(n). This is known as an asymptotic upper bound. For set membership, we write h(n)=O(f(n)) and not h(n)∈O(f(n)).

Examples

A list of expressions and their big O bounds are given below, and below this list is a graph showing the growth of some functions.

• 2=O(1)
• 4x+2=O(x)
• 3x2+4x+2=O(x2)

References

T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms. MIT Press, 1990.