Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Thanks.

share|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
add comment

2 Answers 2

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.