Sign up ×
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.

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.

share|cite|improve this question
Similar question on cs.SE. – Raphael Jun 18 '12 at 18:26

2 Answers 2

up vote 7 down vote accepted

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

share|cite|improve this answer
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

enter image description hereenter image description herethe given problem is best fit on master theorem

share|cite|improve this answer

protected by Community Oct 17 at 3:29

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.