Big o

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation.

Definition

In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows. On the other hand, in mathematics, it is used to describe how closely a finite series approximates a given function.

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.

The letter O is used because the growth rate of a function is also referred to as the order of the function. A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.

Usage

Big O notation is used in many fields to quantify the scale or complexity of a task. In computer science, it is often used to describe the complexity of algorithms, which can have significant implications for the practicality of different approaches to solving a problem.

In mathematics, big O notation is often used to approximate functions. This can be useful in many areas, such as in the derivation of mathematical models.

Examples

For example, the time (or the number of steps) it takes to complete a problem of size n might be found to be T(n) = 4n^2 − 2n + 2. As n grows large, the n^2 term will come to dominate, so that all other terms can be neglected — for instance when n > 5 the value of the other terms become insignificant in comparison to the term 4n^2. We say that T(n) is a "big-oh" of (n^2) and write T(n) = O(n^2).

See also

• Time complexity
• Space complexity
• Computational complexity theory
• Analysis of algorithms