21 - Orders of Magnitude

Big $O$ notation

Let $(a_n),(b_n)$ be sequences
Then $a_n=O(b_n)$ as $n\to \infty$ if

$$\exists C\in {\mathbb{R}}^{>0}\text{ and there is }N\text{ such that if }n\ge N\text{ then }|a_n|\le C|b_n|$$

Little $O$ notation

Let $(a_n),(b_n)$ be sequences
If $b_n\ne 0$ for all $n$ (or all sufficiently large $n$)

Then $a_n=o(b_n)$ as $n\to \infty$ if

$$\frac{a_n}{b_n}\to 0\text{ as }n\to \infty$$