Editing Big O notation (section)

== Use ==
Big O notation has two main areas of application:
* In [[mathematics]], it is commonly used to describe [[#Infinitesimal asymptotics|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 [[#Infinite asymptotics|analysis of algorithms]].<ref name=":0" />

In both applications, the function <math>g(x) </math> appearing within the <math>O(\cdot) </math> is typically chosen to be as simple as possible, omitting constant factors and lower order terms.

There are two formally close, but noticeably different, usages of this notation:{{citation needed|date=April 2021}}
* [[Infinity|infinite]] asymptotics
* [[infinitesimal]] asymptotics.

This distinction is only in application and not in principle, however—the formal definition for the "big O" is the same for both cases, only with different limits for the function argument.{{original research inline|date=April 2021}}

=== Infinite asymptotics ===
{{Dark mode invert|image=yes|[[File:comparison computational complexity.svg|thumb|Graphs of functions commonly used in the analysis of algorithms, showing the number of operations <math>N </math> versus input size <math>n </math> for each function]]}}
Big O notation is useful when [[analysis of algorithms|analyzing algorithms]] for efficiency. For example, the time (or the number of steps) it takes to complete a problem of size <math> n</math> might be found to be <math> T(n)=4n^2-2n+2 </math>. As <math> n</math> grows large, the <math> n^2</math> [[Summand|term]] will come to dominate, so that all other terms can be neglected—for instance when <math> n=500</math>, the term <math> 4n^2</math> is 1000 times as large as the <math> 2n</math> term. Ignoring the latter would have negligible effect on the expression's value for most purposes. Further, the [[coefficient]]s become irrelevant if we compare to any other [[Orders of approximation|order]] of expression, such as an expression containing a term <math> n^3</math> or <math> n^4</math>. Even if <math> T(n)=1000000n^2</math>, if <math> U(n)=n^3</math>, the latter will always exceed the former once {{mvar|n}} grows larger than <math> 1000000</math>, ''viz.'' <math display="block"> T(1000000)=1000000^3=U(1000000)</math>. Additionally, the number of steps depends on the details of the machine model on which the algorithm runs, but different types of machines typically vary by only a constant factor in the number of steps needed to execute an algorithm. So the big O notation captures what remains: we write either
:<math>T(n)= O(n^2) </math>
or
:<math>T(n) \in O(n^2) </math>
and say that the algorithm has ''order of {{math|n<sup>2</sup>}}'' time complexity. The sign "{{math|1==}}" is not meant to express "is equal to" in its normal mathematical sense, but rather a more colloquial "is", so the second expression is sometimes considered more accurate (see the "[[#Equals sign|Equals sign]]" discussion below) while the first is considered by some as an [[abuse of notation]].<ref name="clrs3" />

=== Infinitesimal asymptotics ===
Big O can also be used to describe the [[Taylor series#Approximation error and convergence|error term]] in an approximation to a mathematical function. The most significant terms are written explicitly, and then the least-significant terms are summarized in a single big O term.  Consider, for example, the [[Exponential function#Formal definition|exponential series]] and two expressions of it that are valid when {{mvar|x}} is small:
<math display=block>\begin{align}
e^x &=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\dotsb &&\text{for all finite } x\\[4pt]
    &=1+x+\frac{x^2}{2}+O(x^3)                                &&\text{as } x\to 0\\[4pt]
    &=1+x+O(x^2)                                              &&\text{as } x\to 0
\end{align}</math>
The middle expression (the one with <math> O(x^3)</math>) means the absolute-value of the error <math> e^x-(1+x+\frac{x^2}{2})</math> is at most some constant times <math> |x^3!|</math> when <math>x </math> is close enough to <math> 0</math>.