Big O notation: Difference between revisions
imported>Subpagination Bot m (Add {{subpages}} and remove any categories (details)) |
imported>Hendra I. Nurdin m (space) |
||
| 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'' (respectively, <math>f_n</math>) and ''g'' (respectively, <math>g_n</math>) are real valued functions of the real numbers (respectively, sequences) then the notation <math>f(t)=O(g(t))</math> (respectively, <math>f_n=O(g_n)</math>) denotes that there exist a positive real number (respectively, integer) ''T'' and a positive constant ''C'' such that <math>|f(t)|\leq C |g(t)|</math> for all <math>t>T</math>(respectively, <math>|f_n| \leq C |g_n|</math> for all n>T). | More formally, if ''f'' (respectively, <math>f_n</math>) and ''g'' (respectively, <math>g_n</math>) are real valued functions of the real numbers (respectively, sequences) then the notation <math>f(t)=O(g(t))</math> (respectively, <math>f_n=O(g_n)</math>) denotes that there exist a positive real number (respectively, integer) ''T'' and a positive constant ''C'' such that <math>|f(t)|\leq C |g(t)|</math> for all <math>t>T</math> (respectively, <math>|f_n| \leq C |g_n|</math> 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 [[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>. | 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>. | ||
Revision as of 00:40, 10 October 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 .
