The Analysis of Data, volume 1

Metric Spaces: Growth of Functions

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$.