# What sequences / algorithms does $O(N \log\log N)$ limit?

Considering the big-o-notation, there are a variety of algorithms that have the $O(N \log N)$ computational complexity; such algorithms are for example the merge sort, fast fourier transform, etc.

The computational complexity $O(N\log(\log N)))$ is seen much less. What algorithms / sequences are limited by this time complexity?

For example, consider the usual divide-and-conquer algorithms. Those algorithms usually split the original problem of $O(N^2)$ complexity recursively into two halves and solve each halve separately, recuding the needed time to $O(N\log N)$. In order to get the $O(N log(log(N)))$ complexity, how much should the problem size be reduced on each step?

• Remember, Big-O notation only gives an upper bound. So, any algorithm that has, for instance, $O(n)$ complexity also has $O(n\log\log n)$. You may wish to rephrase in terms of $\Theta$. – Nick Peterson Jun 23 '13 at 14:26
• – Did Jun 23 '13 at 19:47

You have to reduce the problem size rather quickly. For instance, the recurrence $$T(N) = \sqrt{N}\, T(\sqrt{N}) + N$$ when applied to $N=2^{2^k}$ with $T(2)=2$ has the exact solution $$T(2^{2^k}) = 2^{2^k}(1+k)$$ so for these values we'll have $T(N) = N(1+\lg\lg N)$, where $\lg x$ denotes $\log_2 x$. For other values of $N$ it's not too difficult to show that $T(N)=\Theta(N\,\log\log N)$.
Not that it matters for your question, but I frequently use this as an exercise to demonstrate that there are recurrence relations for which the Master Theorem doesn't apply but which are amenable to proof by induction (on $k$, in this case), if one is given the purported closed form solution.