Solution of $T(n)=2T(n/2) + n\log(\log n)$ 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.
 A: 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}
A: 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.
