Asymptotic notations

Introduction
Let's start with some motivating examples showing how these notations are used.

Using Taylor series expansions, we have

$\begin{align} e^x &=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\cdots\:\: \text{for all x}\\ &=1+x+O(x^2)\:\:\text{as}\: x \to 0 \end{align}\\ \Rightarrow e^x \sim 1+x$

$\begin{align}\log(1+x)&=x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}+\cdots\\ &=x+O(x^2) \end{align}\\ \Rightarrow \log(1+x) \sim x$

The symbol $O(x^2)$ means that the remainder is bounded by $Ax^2$ as $x$ tends to $0$ for some finite $A$.

Big O notation is a symbolism used in complexity theory, computer science, and mathematics to describe the asymptotic behavior of functions. It tells you how fast a function grows or declines. The letter O is used because the rate of growth of a function is also called its order.

If $x_n=3n^2-2n+3$, then $x_n=o(n^3)$, $x_n=O(n^2)$ and $x_n \sim 3n^2\: \text{as}\: n \to \infty$.

o-order is less useful than O-order. For example, $\sin z = z + o(z^2)$ as $z \to 0$ tells us that $\sin z - z \to 0$ faster than $z^2$, however $\sin z = z + O(z^3)$, tells us specifically that $\sin z - z \to 0$ like $z^3$.

Definitions
The symbols $O$, $o$ and $\sim$ were first used by E. Landau and P. Du Bois- Reymond.
Suppose $f(z)$ and $g(z)$ are functions of the continuous complex variable $z$ defined on some domain $D \subset \mathbb{C}$ and possess limits as $z \to z_0$ in $D$.

Asymptotically bounded
$f(z)=O(g(z))$ $\: \text{as}\:$ $z \to z_0$ means that there exists constants $K \geq 0$ and $\delta >0$ such that, for $0<|x-x_0|<\delta$, $|f(z)| \leq K |g(z)|$.

Asymptotically smaller
$f(z)=o(g(z))$ $\: \text{as}\:$ $z \to z_0$ means that for all $\epsilon >0$ such that, for $0<|z-z_0|<\epsilon$, $|f(z)|\leq \epsilon |g(z)|$
Equivalently this means that for non-zero $g(z)$ in a neighbourhood of $z_0$ except possibly at $z_0$, then as $z \to z_0$: $\large \frac{f(z)}{g(z)} \to 0$.

Asymptotically equal
$f(z) \sim g(z)$ $\: \text{as}\:$ $z \to z_0$ means that for non-zero $g(z)$ in a neighbourhood of $z_0$ except possibly at $z_0$, then as $z \to z_0$: $\large \frac{f(z)}{g(z)} \to 1$.

Applications
Approximations & finding limits
This notation saves us the trouble of computing many arithmetic operations. Meanwhile, it avoids the ambiguity of using "the three dots".
$f(x) \sim g(x)$ when $x \to \infty \Rightarrow \large\lim\limits_{x \to \infty} \frac{f(x)}{g(x)}=1$
This is why we can use the following approximations in multiplicative situations.



Computer science -- Analysis of algorithms [later]