April | 2010 | Hackalog

Little-oh

April 24, 2010 at 11:26 pm (Math) (algorithms, analysis, little oh)

Why is it impossible to find a nontrivial example of someone using little-oh notation?

Recall, little oh is defined as follows. We write $f(x) = o(g(x))$ if

$\lim _{x \to \infty} \frac{f(x)}{g(x)} = 0$ .

Let’s say I want to get rid of silly little terms like $\log \log x$ . Notice that:

$\log\log x = e^{\log\log\log x} = e^{(\log\log x) \frac{\log \log \log x}{\log \log x}} = (\log x)^{\frac{\log \log \log x}{\log \log x}}$ .

Of course, $\lim_{x \to \infty} \frac{\log \log \log x}{\log \log x} = 0$ , so this exponent is $o(1)$ .

Using this trick, we can rewrite expressions in this way:

$\log x \log \log x = (\log x)^{1+o(1)},$

and hence all the ugly little log terms have been swept under the rug.