Big O notation

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, $f_{n}$) and g (respectively, $g_{n}$) are real valued functions of the real numbers (respectively, sequences) then the notation $f(t)=O(g(t))$ (respectively, $f_{n}=O(g_{n})$) denotes that there exist a positive real number (respectively, integer) T and a positive constant C such that $|f(t)|\leq C|g(t)|$ for all $t>T$(respectively, $|f_{n}|\leq C|g_{n}|$ 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 $t_{0}$ the notation $f(t)=O(g(t-t_{0}))$, 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 $|f(t)|\leq C|g(t-t_{0})|$ on some neighbourhood N of $t_{0}$.

See also

Little o notation