Big O Notation

/bɪɡ oʊ noʊˈteɪʃən/big O no·ta·tionnoun

Algorithms CoreFoundational

Definition

1.[in computer science] a way of describing how the cost of an algorithm grows as its input grows, keeping only the dominant term and discarding constants.

Insertion into a balanced tree is O(log n) in Big O notation.

Formal statement

f(n) = O(g(n)) iff f(n) <= c*g(n) for all n >= n0

An upper bound on growth, not a measure of actual running time.

Etymology

The symbol is Edmund Landau's, from German Ordnung 'order', in his 1909 work; Paul Bachmann had introduced the notation in 1894. Donald Knuth brought it into algorithm analysis in the 1960s.

Synonyms

asymptotic notationsense 1 · Near

References

Knuth, D. (1976). Big Omicron and Big Omega and Big Theta.ACM SIGACT News, 8(2), 18–24.