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?


  • $\begingroup$ Please state the problem in the body of your question, not just in the title. $\endgroup$ – Zev Chonoles Jun 8 '12 at 7:17

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}

| 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.

| cite | improve this answer | |

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.