Take the 2-minute tour ×
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|improve this question
    
Similar question on cs.SE. –  Raphael Jun 18 '12 at 18:26
    
Can some one Solve the recurrence T(n)=T(n√)+2. Assume that T(n) is constant for n≤2. Using both Master Theorem and backward substitution –  Andre Cadogan Nov 23 '12 at 8:25
    
@AndreCadogan. Welcome to the site! Generally, comments here should be pertinent to the question or answer, meaning that you should post this as a separate question (click on the "ASK QUESTION" text at the top of the page. Don't bother in this specific instance, since there's already an answer to a nearly-identical question here. –  Rick Decker Dec 15 '13 at 20:18
add comment

1 Answer

up vote 2 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|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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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