15 - Order Notation

Big O Notation

Let $f(x),g(x)$ be functions

$$f(x)=O(g(x))\text{ as }x\to x_0\text{if }\exists A>0\text{ such that }|f(x)|<A|g(x)|$$

for all $x$ sufficiently close to $x_0$

Note that it is read as $f$ is of order $g$

Examples

1. $\sin (2x)=O(x)$ as $x\to 0$
2. $3x+x^3=O(x)$ as $x\to 0$
3. $\log x=O(x-1)$ as $x\to 1$

Twiddles Notation

Let $f(x),g(x)$ be functions

$$f(x)\sim g(x)\text{ if }\frac{f(x)}{g(x)}\to 1\text{ as }x\to x_0$$

Note that it is read as $f$ is asymptotic to $g$ as $x\to x_0$

Examples

1. $\sin (2x)\sim 2x$ as $x\to 0$
2. $x+e^{-x}$ as $x\to \infty$

Little o Notation

Let $f(x),g(x)$ be functions

$$f(x)=o(g(x))\text{ as }x\to x_0\text{ if }\underset{x\to x_0}{\lim }\frac{f(x)}{g(x)}=0$$

Note that it is read as $f$ is much smaller than $g$ in limit as $x\to x_0$

Examples

1. $9x^2-4x^5=o(x)$ as $x\to 0$
2. $\frac{3}{x^2}-3e^{-x}=o\left(\frac{1}{x}\right)$ as $x\to \infty$