1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Nick Peterson Jun 23 '13 at 14:26
  • $\begingroup$ Related. $\endgroup$ – Did Jun 23 '13 at 19:47
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.