<s>[INST] How to solve this recurrence $T(n) = 2T(n/2) + n\log n$ How can I solve the recurrence relation $T(n) = 2T(n/2) + n\log n$? It almost matches the Master Theorem except for the $n\log n$ part.
 [/INST] Let us take $n = 2^m$. Then we have the recurrence $$T(2^m) = 2T(2^{m-1}) + 2^m \log_2(2^m) = 2T(2^{m-1}) + m 2^m$$
Calling $T(2^m)$ as $f(m)$, we get that
\begin{align}
f(m) & = 2 f(m-1) + m 2^m\\
& = 2(2f(m-2) + (m-1)2^{m-1}) + m2^m\\
& = 4f(m-2) + (m-1)2^m + m2^m\\
& = 4(2f(m-3) +(m-2)2^{m-2}) + (m-1)2^m + m2^m\\
& = 8f(m-3) +(m-2)2^m + (m-1)2^m + m2^m\\
\end{align}
Proceeding on these lines, we get that
\begin{align}
f(m) &= 2^m f(0) + 2^m (1+2+3+\cdots+m) = 2^m f(0) + \dfrac{m(m+1)}{2}2^m\\
& = 2^m f(0) + m(m+1)2^{m-1}
\end{align}
Hence, $T(n) = n T(1) + n \left(\dfrac{\log_2(n) (1+\log_2(n))}{2} \right) = \mathcal{\Theta}(n \log^2 n)$.
</s>