Big O notation: Difference between revisions
imported>Hendra I. Nurdin m (updated link to little o notation) |
imported>Pat Palmer (adding Computers Workgroup) |
||
Line 10: | Line 10: | ||
[[Category:Mathematics Workgroup]] | [[Category:Mathematics Workgroup]] | ||
[[Category:Computers Workgroup]] | |||
[[Category: CZ Live]] | [[Category: CZ Live]] |
Revision as of 11:28, 23 September 2007
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 (respectively, ) and g (respectively, ) are real valued functions of the real numbers (respectively, sequences) then the notation (respectively, ) denotes that there exist a positive real number (respectively, integer) T and a positive constant C such that for all (respectively, for all n>T).
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 .