Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am struggling to solve this equation: $$T(n)=2T(n/2) + n\log(\log n).$$ I concluded that the Master Theorem does not apply in this situation so I tried to successively substitute the terms in order to solve this equation but cannot proceed. Could somebody tell me what would be the best way to solve this?


share|cite|improve this question
Please state the problem in the body of your question, not just in the title. – Zev Chonoles Jun 8 '12 at 7:17
up vote 2 down vote accepted

We are given that $$T(n) = 2 T(n/2) + n \log_2(\log_2(n))$$ (Note that if we take $\log$ to the base $2$ or to the base $e$, the only difference is in the coefficient of the leading order term).

Let $n = 2^k$. Call $T(n) = g(k)$. Then we have \begin{align} g(k) & = 2g(k-1) + 2^k \log_2(k)\\ & = 2 (2g(k-2) + 2^{k-1} \log_2(k-1)) + 2^k \log_2(k)\\ & = 4 g(k-2) + 2^k \log_2(k-1) + 2^k \log_2(k)\\ & = 4 (2g(k-3) + 2^{k-2} \log_2(k-2))+ 2^k \log_2(k-1) + 2^k \log_2(k)\\ & = 8 g(k-3) + 2^k \log_2(k-2) + 2^k \log_2(k-1) + 2^k \log_2(k) \end{align} Hence, in general, \begin{align} g(k) & = 2^k g(0) + 2^k \left( \log_2(1) + \log_2(2) + \log_2(3) + \cdots + \log_2(k)\right)\\ & = 2^k g(0) + 2^k \log_2(k!) \end{align} Now from Stirling's formula, we have that $$k! \sim C \sqrt{k} \left(\dfrac{k}{e} \right)^k$$ Hence, $$\log_2(k!) = k \log_2(k) - k \log_2(e) + \dfrac12 \log_2(k) + \mathcal{O}(1)$$ \begin{align} g(k)& = 2^k g(0) + 2^k \left( k \log_2(k) -k \log_2(e) + \dfrac12 \log_2(k) + \mathcal{O}(1) \right)\\ & = 2^k k \log_2(k) - k2^k \log_2(e) + 2^{k-1} \log_2(k) + \mathcal{O} \left(2^k \right) \end{align} Now plug in $k = \log_2(n)$, to get \begin{align} T(n) & = n \log_2(n) \log_2(\log_2 n) - n \log_2(n) \log_2(e) + \dfrac{n}2 \log_2(\log_2 n) + \mathcal{O}(n) \end{align}

share|cite|improve this answer

Here's a 'straightforward' (i.e. non-rigorous) partial answer that may help you build your intuition. Assume all logs are base 2. By expanding $m$ times you can find that

$$T(n) = 2^m T(n/2^m) + n\sum_{j=0}^{m-1} \log\log(n/2^j)$$

so if we let $n=2^k$ and $m=k$, then

$$T(n) = n T(1) + n\sum_{j=0}^{\log n - 1} \log\log (n/2^j)$$

This gives you the easy bound

$$\begin{align} T(n) & < n T(1) + n\sum_{j=0}^{\log n-1} \log \log n \\ & < nT(1) + n\log n \log\log n \end{align}$$

and so you definitely have $T(n)=O(n\log n \log \log n)$.

By being more careful when bounding the sum (e.g. see Marvis's answer) you will be able to prove that $T(n)=\Theta(n\log n\log \log n)$ as well.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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