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

-
– Raphael Jun 18 '12 at 18:26
It satisfies the Case 2 of Master Theorem Case 2: f(n) = Theta O(n^log_b(a) (log_2(n))^k ) for some k >= 0 T(n) = O(n^log_b(a) (log_2(n))^(k+1) ) In our case f(n) = n^(log_2(2)) (log n) ^ 1, Hence k = 1 T(n) = Theta O(n (log_2(n) ) ^ 2) – vCillusion Mar 23 at 11:02

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

-
Thank you. But if $T(2^m) = f(m)$, then isn't $T(2^{m-1}) = f(m/2)$ ? How do you get $f(m-1)$? – cody Jun 18 '12 at 1:31
@cody $T(2^m) = f(m)$. Now replace $m$ by $m-1$, we then get $T(2^{m-1}) = f(m-1)$. – user17762 Jun 18 '12 at 1:41
I see. Thank you. So the trick to these recurrence relation is to transform them from the T(.) form to one of the summation series, right? – cody Jun 18 '12 at 2:01
... and then prove by induction that the closed form is correct. – Raphael Jun 18 '12 at 18:26
@cody Yes. and as Raphael points out use induction/recursion. – user17762 Jun 18 '12 at 18:28

the given problem is best fit on master theorem

-

## protected by Community♦Oct 17 '15 at 3:29

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?