Big O notation - Revision history

Karl Jones at 00:46, 28 October 2016

2016-10-28T00:46:53Z

Karl Jones at 00:38, 28 October 2016

2016-10-28T00:38:40Z

Karl Jones: /* See also */

2016-10-16T17:53:24Z

‎See also

Karl Jones at 16:34, 6 September 2016

2016-09-06T16:34:02Z

Karl Jones: Created page with "In mathematics, '''Big O notation''' is a mathematical notation that describes the limiting behavior of a function when..."

2016-09-06T16:33:18Z

Created page with "In mathematics, '''Big O notation''' is a mathematical notation that describes the limiting behavior of a function when..."

New page

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 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.[3] 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.

== See also ==

* [[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
* [[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]]

== External links ==

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

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

@@ 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.
-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.
-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.
 Big O notation is also used in many other fields to provide similar estimates.
 == See also ==
 * [[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
 * [[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]]
 * [[Time complexity]]
 == External links ==
@@ Line 32: / Line 41: @@
 * [https://en.wikipedia.org/wiki/Big_O_notation Big O notation] @ Wikipedia
 [[Category:Computer science]]
 [[Category:Mathematics]]

@@ Line 3: / Line 3: @@
 == 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.
+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.[3] 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.