# Difference between revisions of "Big O notation"

(Big O notation moved to Complexity of algorithms: per math author request and computer editor approval) |
Jitse Niesen (Talk | contribs) (move See also section to subpage) |
||

(21 intermediate revisions by 7 users not shown) | |||

Line 1: | Line 1: | ||

− | + | {{subpages}} | |

+ | |||

+ | 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 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 ''n'' big enough. | ||

+ | <!-- <math>|a_n|\le C |b_n|</math> for all <math>n</math> big enough.--> | ||

+ | |||

+ | The big O notation is also often used to indicate that the absolute value of a real valued function around some [[topological space#Some topological notions|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 <math>t_0</math> the notation <math>f(t)=O(g(t-t_0))</math>, where ''g''(''t'') is a function which is [[continuity|continuous]] at ''t'' = 0 with ''g''(0) = 0, denotes that there exists a real positive constant ''C'' such that <math>|f(t)|\leq C|g(t-t_0)|</math> on ''some'' neighbourhood ''N'' of <math>t_0</math>. |

## Latest revision as of 11:18, 15 July 2008

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

Similarly, if and are two numerical sequences then means that for all *n* 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 .