View source for Big O notation

In [[mathematics]], '''Big O notation''' is a mathematical notation that describes the [[Asymptotic analysis|limiting behavior]] of a [[Function (mathematics)|function]] when the argument tends towards a particular value or infinity.

== Description ==

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.

In [[computer science]], big O notation is used to [[Computational complexity theory|classify algorithms]] by how they respond to changes in input size, such as how the processing time of an algorithm changes as the problem size becomes extremely large.

In [[analytic number theory]] it is used to estimate the "error committed" while replacing the asymptotic size of an [[Arithmetic function|arithmetical function]] by the value it takes at a large finite argument. A famous example is the problem of estimating the remainder term in the [[prime number theorem]].

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 order of the function. A description of a function in terms of big O notation usually only provides an [[Upper and lower bounds|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.

Big O notation has two main areas of application. In mathematics, it is commonly used to describe how closely a finite series approximates a given function, especially in the case of a truncated [[Taylor series]] or [[asymptotic expansion]]. In [[computer science]], it is useful in the [[analysis of algorithms]]. 

== See also ==

* [[Analysis of algorithms]]
* [[Analytic number theory]]
* [[Arithmetic function]]
* [[Asymptotic analysis]]
* [[Asymptotic expansion]]: Approximation of functions generalizing Taylor's formula
* [[Asymptotically optimal]]: A phrase frequently used to describe an algorithm that has an upper bound asymptotically within a constant of a lower bound for the problem
* [[Big O in probability notation]]: Op,op
* [[Computational complexity theory]]
* [[Limit superior and limit inferior]]: An explanation of some of the limit notation used in this article
* [[Nachbin's theorem]]: A precise method of bounding complex analytic functions so that the domain of convergence of integral transforms can be stated
* [[Orders of approximation]]
* [[Prime number theorem]]
* [[Taylor series]]
* [[Time complexity]]
* [[Upper and lower bounds]]

== External links ==

* [https://en.wikipedia.org/wiki/Big_O_notation Big O notation] @ Wikipedia

[[Category:Complexity]]
[[Category:Computer science]]
[[Category:Mathematics]]