Editing Big O notation (section)

== Formal definition ==
Let <math>f,</math> the function to be estimated, be a [[Real number|real]] or [[Complex number|complex]] valued function, and let <math>g,</math> the comparison function, be a real valued function. Let both functions be defined on some [[Bounded set|unbounded]] [[subset]] of the positive [[real number]]s, and <math>g(x)</math> be non-zero (often, but not necessarily, strictly positive) for all large enough values of <math>x.</math><ref name=LandauO>{{cite book |first=Edmund |last=Landau |author-link=Edmund Landau |title=Handbuch der Lehre von der Verteilung der Primzahlen |publisher=B.G. Teubner |year=1909 |location=Leipzig |trans-title=Handbook on the theory of the distribution of the primes |language=de |page=31 | url=https://archive.org/stream/handbuchderlehre01landuoft#page/31/mode/2up }}</ref> One writes
<math display="block">f(x) = O\bigl( g(x) \bigr) \quad \text{ as } x \to \infty</math>
and it is read "<math>f(x)</math> is big&nbsp;O of <math>g(x) </math>" or more often "<math>f(x) </math> is of the order of <math>g(x) </math>" if the [[absolute value]] of <math>f(x) </math> is at most a positive constant multiple of the absolute value of <math>g(x)</math> for all sufficiently large values of <math>x.</math> That is, <math>f(x) = O\bigl(g(x) \bigr) </math> if there exists a positive real number <math>M </math> and a real number <math>x_0 </math> such that
<math display="block">|f(x)| \le M\ |g(x)| \quad \text{ for all } x \ge x_0 ~.</math>
In many contexts, the assumption that we are interested in the growth rate as the variable <math>\ x\ </math> goes to infinity or to zero is left unstated, and one writes more simply that
<math display="block">f(x) = O\bigl(g(x) \bigr).</math>
The notation can also be used to describe the behavior of <math>f</math> near some real number <math>a </math> (often, <math>a = 0 </math>): we say
<math display="block">f(x) = O\bigl( g(x) \bigr) \quad \text{ as }\ x \to a</math>
if there exist positive numbers <math>\delta </math> and <math>M</math> such that for all defined <math>x </math> with <math>0 < |x-a| < \delta,</math>
<math display="block">|f(x)| \le M |g(x)|.</math>
As <math>g(x) </math> is non-zero for adequately large (or small) values of <math>x,</math> both of these definitions can be unified using the [[limit superior]]:
<math display="block">f(x) = O\bigl( g(x) \bigr) \quad \text{ as }\ x \to a  </math>
if
<math display="block">\limsup_{x\to a} \frac{\left|f(x)\right|}{\left|g(x)\right|} < \infty.</math>
And in both of these definitions the [[limit point]] <math>a </math> (whether <math>\infty </math> or not) is a [[cluster point]] of the domains of <math>f</math> and <math>g,</math> i.&nbsp;e., in every neighbourhood of <math>a</math> there have to be infinitely many points in common. Moreover, as pointed out in the article about the [[Limit inferior and limit superior#Real-valued functions|limit inferior and limit superior]], the <math>\textstyle \limsup_{x\to a} </math> (at least on the [[extended real number line]]) always exists.

In computer science, a slightly more restrictive definition is common: <math>f </math> and <math>g </math> are both required to be functions from some unbounded subset of the [[natural numbers|positive integers]] to the nonnegative real numbers; then <math>f(x) = O\bigl( g(x) \bigr) </math> if there exist positive integer numbers <math>M </math> and <math>n_0 </math> such that <math>|f(n)| \le M |g(n)| </math> for all <math>n \ge n_0.</math><ref>{{cite book | first=Michael | last=Sipser | year=1997 | title=Introduction to the Theory of Computation | location=Boston, MA | publisher=PWS Publishing |page=227, def.&nbsp;7.2 }}</ref>