Little-o notation, written as \(\littleo{g(n)}\), is a stronger statement than Big O notation. It implies that \(g(x)\) grows much faster than \(f(x)\). It’s defined as:

\[f(x) = \littleo{g(x)} \overset{\Delta}{=} \lim_{x \to \infty} \frac{f(x)}{g(x)} = 0\]

Relationship with Big-O notation

\[\begin{align}3n^3 &= \bigo{n^3} \\ 3n^3 &\ne \littleo{n^3} \\ 3n^3 &= \littleo{n^4}\end{align}\]

To use an analogy:

\[\begin{align}f(n) &\in \bigo{g(n)} &\implies f(n) &\le g(n) \\ f(n) &\in \littleo{g(n)} &\implies f(n) &< g(n)\end{align}\]

References