Big O notation

related topics
{math, number, function}
{rate, high, increase}

In mathematics, computer science, and related fields, big-O notation (also known as big Oh notation, big Omicron notation, Landau notation, Bachmann–Landau notation, and asymptotic notation) (along with the closely related big-Omega notation, big-Theta notation, and little o notation) describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.

Although developed as a part of pure mathematics, this notation is now frequently also used in the analysis of algorithms to describe an algorithm's usage of computational resources: the worst case or average case running time or memory usage of an algorithm is often expressed as a function of the length of its input using big O notation. This allows algorithm designers to predict the behavior of their algorithms and to determine which of multiple algorithms to use, in a way that is independent of computer architecture or clock rate. Because big O notation discards multiplicative constants on the running time, and ignores efficiency for low input sizes, it does not always reveal the fastest algorithm in practice or for practically-sized data sets, but the approach is still very effective for comparing the scalability of various algorithms as input sizes become large.

A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function. Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates. Big O notation is also used in many other fields to provide similar estimates.

Contents

Full article ▸

related documents
Linear programming
Combinatory logic
Relational model
Prolog
System of linear equations
Laplace transform
Red-black tree
Banach–Tarski paradox
Formal power series
Quadratic reciprocity
Spinor
Lebesgue integration
Wikipedia:Free On-line Dictionary of Computing/R - S
Lambda calculus
P-adic number
Determinant
Fibonacci number
Trigonometric functions
Travelling salesman problem
Binomial coefficient
Discrete cosine transform
Grothendieck topology
Pythagorean triple
Field (mathematics)
Original proof of Gödel's completeness theorem
Μ-recursive function
Group theory
Linked list
Riemann integral
Bernoulli number