Big O notation

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. Big O is a member of a family of notations invented by German mathematicians Paul Bachmann,^[1] Edmund Landau,^[2] and others, collectively called Bachmann–Landau notation or asymptotic notation. The letter O was chosen by Bachmann to stand for Ordnung, meaning the order of approximation.

In computer science, big O notation is used to classify algorithms according to how their run time or space requirements ^[a] grow as the input size grows.^[3] In analytic number theory, big O notation is often used to express a bound on the difference between an arithmetical function and a better understood approximation; one well-known example is the remainder term in the prime number theorem. Big O notation is also used in many other fields to provide similar estimates.

Big O notation characterizes functions according to their growth rates: different functions with the same asymptotic 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.

Associated with big O notation are several related notations, using the symbols $o$ , $\Omega$ , $\omega$ , and $\Theta$ to describe other kinds of bounds on asymptotic growth rates.^[3]

^ Cite error: The named reference Bachmann was invoked but never defined (see the help page).
^ Cite error: The named reference Landau was invoked but never defined (see the help page).
^ ^a ^b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). "Growth of Functions". Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. pp. 23–41. ISBN 978-0-262-53091-0.

Cite error: There are <ref group=lower-alpha> tags or {{efn}} templates on this page, but the references will not show without a {{reflist|group=lower-alpha}} template or {{notelist}} template (see the help page).

[Bachmann-1] Cite error: The named reference Bachmann was invoked but never defined (see the help page).

[Landau-2] Cite error: The named reference Landau was invoked but never defined (see the help page).

[:0-4] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). "Growth of Functions". Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. pp. 23–41. ISBN 978-0-262-53091-0.

[1]

[2]

[a]

[3]