Big O notation: Difference between revisions
imported>Jitse Niesen (move See also section to subpage) |
mNo edit summary |
||
| Line 9: | Line 9: | ||
<!-- <math>|a_n|\le C |b_n|</math> for all <math>n</math> 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>. | 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>.[[Category:Suggestion Bot Tag]] | ||
Latest revision as of 11:01, 18 July 2024
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 .
