Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
    
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
up vote 8 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
1  
@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 '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?

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