The Little-O measure

Any formal treatment of complexity often begins with this. The concept here is easy. Let $\Phi(i)$ be an algorithm with input $i$ (We assume this from here onwards). Then, let $f(n) \geq 0$ be a complexity measure of $\Phi(i)$, such that $f(n) \to \infty$. Define:

$$f \in o(g(n)) \iff \lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$$

Let us exemplify what we mean here. Suppose $\Phi(i)$ takes $f(n) = n^3 + 3 n^2 + 1$ to run. Then, we can say that $f(n)$ is $o(n^4)$ or $o(e^n)$. You can check that it satisfies the limit above. We cannot, however, talk about it being $O(n^3)$.

This notation is infrequently used. However, it can be good to know what it means.