Actions

::Big O notation

::concepts



Example of Big O notation: f(x) ∈ O(g(x)) as there exists c > 0 (e.g., c = 1) and x0 (e.g., x0 = 5) such that f(x) < cg(x) whenever x > x0.

In mathematics, big 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. It is a member of a larger family of notations that is called Landau notation, Bachmann–Landau notation (after Edmund Landau and Paul Bachmann),<ref name="Beigi2011">{{#invoke:citation/CS1|citation |CitationClass=book }}</ref><ref name="Holmes2012">{{#invoke:citation/CS1|citation |CitationClass=book }}</ref> or asymptotic notation. In computer science, big O notation is used to classify algorithms by how they respond (e.g., in their processing time or working space requirements) to changes in input size.<ref name=quantumcomplexity>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> In analytic number theory, it is used to estimate the "error committed" while replacing the asymptotic size, or asymptotic mean size, of an arithmetical function, by the value, or mean 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 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 sections
Intro  Formal definition  Example  Usage  Properties  Multiple variables  Matters of notation  Orders of common functions  Related asymptotic notations  Generalizations and related usages  History (Bachmann\u2013Landau, Hardy, and Vinogradov notations)  See also  References and Notes  Further reading  External links  

PREVIOUS: IntroNEXT: Formal definition
<<>>
''x''::''n''    Notation::''o''    ''g''::omega    ''f''::number    Function::infty    Exists::constant

Example of Big O notation: f(x) ∈ O(g(x)) as there exists c > 0 (e.g., c = 1) and x0 (e.g., x0 = 5) such that f(x) < cg(x) whenever x > x0.

In mathematics, big 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. It is a member of a larger family of notations that is called Landau notation, Bachmann–Landau notation (after Edmund Landau and Paul Bachmann),<ref name="Beigi2011">{{#invoke:citation/CS1|citation |CitationClass=book }}</ref><ref name="Holmes2012">{{#invoke:citation/CS1|citation |CitationClass=book }}</ref> or asymptotic notation. In computer science, big O notation is used to classify algorithms by how they respond (e.g., in their processing time or working space requirements) to changes in input size.<ref name=quantumcomplexity>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> In analytic number theory, it is used to estimate the "error committed" while replacing the asymptotic size, or asymptotic mean size, of an arithmetical function, by the value, or mean 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 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 sections
Intro  Formal definition  Example  Usage  Properties  Multiple variables  Matters of notation  Orders of common functions  Related asymptotic notations  Generalizations and related usages  History (Bachmann\u2013Landau, Hardy, and Vinogradov notations)  See also  References and Notes  Further reading  External links  

PREVIOUS: IntroNEXT: Formal definition
<<>>