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:

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

Menaka Lashitha Bandara 2005-04-18