Editing Big O notation (section)

{{Short description|Describes limiting behavior of a function}}
{{Dark mode invert|image=yes|[[File:Big-O-notation.png|300px|thumb|Example of Big O notation: <math>{\color{red}f(x)} = O({\color{blue}g(x)})</math> as <math>x\to\infty</math> since there exists <math>M>0</math> (e.g., <math>M=1</math>) and <math>x_0</math> (e.g.,<math>x_0=5</math>) such that <math>0\leq{\color{red}f(x)}\leq M{\color{blue}g(x)}</math> whenever <math>x\geq x_0</math>.]]}}
{{Order-of-approx}}
{{DISPLAYTITLE:Big ''O'' notation}}
'''Big ''O'' notation''' is a mathematical notation that describes the [[asymptotic analysis|limiting behavior]] of a [[function (mathematics)|function]] when the [[Argument of a function|argument]] tends towards a particular value or infinity. Big O is a member of a [[#Related asymptotic notations|family of notations]] invented by German mathematicians [[Paul Gustav Heinrich Bachmann|Paul Bachmann]],<ref name=Bachmann /> [[Edmund Landau]],<ref name=Landau /> and others, collectively called '''Bachmann–Landau notation''' or '''asymptotic notation'''.  The letter O was chosen by Bachmann to stand for ''[[:wikt:Ordnung#German|Ordnung]]'', meaning the [[order of approximation]].

In [[computer science]], big O notation is used to [[Computational complexity theory|classify algorithms]] according to how their run time or space requirements {{efn|Note that the "size" of the input [data stream] is typically used as an indication of -- [that is, it is assumed to "reflect"] -- how challenging a given ''instance'' is, of the problem to be solved. The amount of [execution] time, and the amount of [memory] space required to compute the answer, (or to "solve' the problem, whatever it is), are seen as indicating -- or "reflecting" -- the difficulty of that ''instance'' of the problem (along with, in some cases, [the 'related' issue, of] the power of the [[algorithm]] that is used by a certain program). For purposes of [[Computational complexity theory]], [[Big O notation|Big ''O'' notation]] is used for [the "order of magnitude" of] all 3 of those: the size of the input [data stream], the amount of [execution] time required, and the amount of [memory] space required.}} grow as the input size grows.<ref name=":0">{{Cite book |last1=Cormen |first1=Thomas H. |author-link=Thomas H. Cormen |title=Introduction to Algorithms |title-link=Introduction to Algorithms |last2=Leiserson |first2=Charles E. |author-link2=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author-link3=Ronald L. Rivest |publisher=MIT Press and McGraw-Hill |year=1990 |isbn=978-0-262-53091-0 |edition=1st |pages=23–41 |chapter=Growth of Functions}}</ref>  In [[analytic number theory]], big O notation is often used to express a bound on the difference between an [[arithmetic function|arithmetical function]] and a better understood approximation; a famous example of such a difference 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 <math> o</math>, <math> \Omega</math>, <math> \omega</math>, and <math> \Theta</math> to describe other kinds of bounds on asymptotic growth rates.<ref name=":0" />