Probability
The Analysis of Data, volume 1
Metric Spaces: Growth of Functions
$
\def\P{\mathsf{P}}
\def\R{\mathbb{R}}
\def\defeq{\stackrel{\tiny\text{def}}{=}}
\def\c{\,|\,}
$
B.5. Growth of Functions
The big-Oh and other growth notations are useful in comparing the asymptotic behavior of two functions $f,g:\R\to\R$. We list below their definitions.
Definition B.5.1.
For two functions $f,g:\R\to \R$ we define the following notations:
\begin{align*}
f=O(g) \text{ as } x\to L \qquad &\text{if} \qquad \limsup_{x\to L} \frac{|f(x)|}{|g(x)|} < \infty\\
f=o(g) \text{ as } x\to L \qquad &\text{if} \qquad
\lim_{x\to L} \frac{f(x)}{g(x)} = 0\\
f\sim g \text{ as } x\to L \qquad &\text{if} \qquad
\lim_{x\to L} \frac{f(x)}{g(x)} = 1\\
f\asymp g \text{ as } x\to L \qquad &\text{if} \qquad
f=O(g)\text{ and } g=O(f).
\end{align*}
Above, $L$ may correspond to a finite limit or an infinite limit: $+\infty, -\infty$. If $L$ is omitted, it is typically assumed to be $+\infty$.
Intuitively, $f=O(g)$ implies that $f$ grows as fast as $g$ or slower, and $f=o(g)$ implies that $f$ grows slower than $g$ does. The definitions above assume that $g(x)$ is non-zero, or at least non-zero as $x \to L$.
Example B.5.1.
We have $f=O(g)$ if and only if $f(x)/g(x)=O(1)$ and $f(x)=o(g(x))$ if and only if $f(x)/g(x)=o(1)$. In this case, the notation 1 corresponds to the constant function $1(x)=1$ for all $x$.
Example B.5.2.
Assuming $n,k>0$, we have $x^n=O(x^k)$ if and only if $k\geq n$ and $x^{-n}=o(x^{-k})$ if and only if $k < n$ (both as $x\to\infty$). We also have $x^n=O(\exp(x))$ and $\exp(-x)=o(x^{-n})$ as $x\to\infty$ for all $n>0$.