Big O notation: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Aleksander Stos
(separate formulation for sequences, less concise but probably more accesible)
imported>Aleksander Stos
(alternative formulation; also deleted adjective positive -- e.g. T might be negative (well, it was OK but unnecessary restrictive))
Line 3: Line 3:
The '''big O notation''' is a mathematical notation to express various bounds concerning asymptotic behaviour of functions. It is often used in particular applications in [[physics]], [[computer science]], [[engineering]] and other [[applied sciences]]. For example, a typical context use in computer science is to express the [[complexity of algorithms]].  
The '''big O notation''' is a mathematical notation to express various bounds concerning asymptotic behaviour of functions. It is often used in particular applications in [[physics]], [[computer science]], [[engineering]] and other [[applied sciences]]. For example, a typical context use in computer science is to express the [[complexity of algorithms]].  


More formally, if ''f'' and ''g''  are real valued functions of the real variable <math>t</math> then the notation <math>f(t)=O(g(t))</math> indicates that there exist a positive real number ''T'' and a positive constant ''C'' such that <math>|f(t)|\leq C |g(t)|</math> for all <math>t>T.</math>
More formally, if ''f'' and ''g''  are real valued functions of the real variable <math>t</math> then the notation <math>f(t)=O(g(t))</math> indicates that there exist a real number ''T'' and a constant ''C'' such that <math>|f(t)|\leq C |g(t)|</math> for all <math>t>T.</math> Equivalently,
:<math>\displaystyle\limsup_{t\to\infty}\frac{|f(t)|}{|g(t)|} \le C.</math>


Similarly, if <math>a_n</math> and <math>b_n</math> are two numerical sequences then <math>a_n=O(b_n)</math> means that  <math>|a_n|\le C |b_n|</math> for all <math>n</math> big enough.
Similarly, if <math>a_n</math> and <math>b_n</math> are two numerical sequences then <math>a_n=O(b_n)</math> means that  <math>|a_n|\le C |b_n|</math> for all <math>n</math> big enough.

Revision as of 04:19, 10 October 2007

This article is a stub and thus not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

The big O notation is a mathematical notation to express various bounds concerning asymptotic behaviour of functions. It is often used in particular applications in physics, computer science, engineering and other applied sciences. For example, a typical context use in computer science is to express the complexity of algorithms.

More formally, if f and g are real valued functions of the real variable then the notation indicates that there exist a real number T and a constant C such that for all Equivalently,

Similarly, if and are two numerical sequences then means that for all big enough.

The big O notation is also often used to indicate that the absolute value of a real valued function around some neighbourhood of a point is upper bounded by a constant multiple of the absolute value of another function, in that neigbourhood. For example, for a real number the notation , where g(t) is a function which is continuous at t=0 with g(0)=0, denotes that there exists a real positive constant C such that on some neighbourhood N of .

See also

Little o notation