Difference between revisions of "Big O notation"
Karl Jones (Talk | contribs) |
Karl Jones (Talk | contribs) |
||
| Line 5: | Line 5: | ||
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. | 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 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 [[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 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. | + | 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. | 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. | + | 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. | 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 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 == | == See also == | ||
| + | * [[Analysis of algorithms]] | ||
| + | * [[Analytic number theory]] | ||
| + | * [[Arithmetic function]] | ||
* [[Asymptotic analysis]] | * [[Asymptotic analysis]] | ||
* [[Asymptotic expansion]]: Approximation of functions generalizing Taylor's formula | * [[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 | * [[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 | * [[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 | * [[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 | * [[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]] | * [[Orders of approximation]] | ||
| + | * [[Prime number theorem]] | ||
| + | * [[Taylor series]] | ||
* [[Time complexity]] | * [[Time complexity]] | ||
| + | * [[Upper and lower bounds]] | ||
== External links == | == External links == | ||
| Line 32: | Line 41: | ||
* [https://en.wikipedia.org/wiki/Big_O_notation Big O notation] @ Wikipedia | * [https://en.wikipedia.org/wiki/Big_O_notation Big O notation] @ Wikipedia | ||
| + | [[Category:Complexity]] | ||
[[Category:Computer science]] | [[Category:Computer science]] | ||
[[Category:Mathematics]] | [[Category:Mathematics]] | ||
Latest revision as of 18:46, 27 October 2016
In mathematics, 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.
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 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 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 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
- Big O notation @ Wikipedia
