Little O Notation

The little 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∈N, c>0, ∃n₀∈N ∀n≥n₀, 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. The fact that this holds for all c means that this bound is not asymptotically tight. This should be compared with the big O notation. For set membership, we write h(n)=o(f(n)) and not h(n)∈o(f(n)).

Examples

2≠o(1)
2=o(x)
4x+2≠o(x)
4x+2=o(x²)
3x²+4x+2≠o(x²)
3x²+4x+2=o(x³)

References

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