<s>[INST] 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.
 [/INST] 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}
</s>