Big O notation

From Citizendium
Revision as of 02:42, 11 October 2007 by imported>Aleksander Stos (commented until found in references)
Jump to navigation Jump to search
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

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 .

See also

Little o notation