Little o notation

The little o notation is a mathematical notation which indicates that the decay (respectively, growth) rate of a certain function or sequence is faster (respectively, slower) than that of another function or sequence. It is often used in particular applications in physics, computer science, engineering and other applied sciences.

More formally, if f (respectively, $f_{n}$) and g (respectively, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_n} ) are real valued functions of the real numbers (respectively, sequences) then the notation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(t)=o(g(t))} (respectively, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_n=O(g_n)} ) denotes that for every real number Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon>0} there exists a positive real number (respectively, integer) $T(\epsilon )$ (note the dependence of T on $\epsilon$) such that $|f(t)|\leq \epsilon |g(t)|$ for all $t>T(\epsilon )$ (respectively, $|f_{n}|\leq \epsilon |g_{n}|$ for all $n>T(\epsilon )$).

The little O notation is also often used to indicate that the absolute value of a real valued function goes to zero around some point at a rate faster than at which the absolute value of another function goes to zero at the same point. For example, suppose that f is a function with $f(t_{0})=0$ for some real number $t_{0}$. Then the notation $f(t)=o(g(t-t_{0}))$, where g(t) is a function which is continuous at t=0 and with g(0)=0, denotes that for every real number $\epsilon >0$ there exists a neighbourhood $N(\epsilon )$ of $t_{0}$ such that $|f(t)|\leq \epsilon |g(t-t_{0})|$ holds on $N(\epsilon )$.

See also

Big O notation