19
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Similar question on cs.SE. $\endgroup$
    – Raphael
    Jun 18 '12 at 18:26
  • $\begingroup$ 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) $\endgroup$
    – vCillusion
    Mar 23 '16 at 11:02
  • $\begingroup$ Master theorem doesn't cover cases where the leftmost function isn't a polynomial. n log n is bounded by n^2, but it doesn't give a theta bound then. $\endgroup$
    – mlanier
    Jan 26 at 19:40
15
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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)$? $\endgroup$
    – cody
    Jun 18 '12 at 1:31
  • 1
    $\begingroup$ @cody $T(2^m) = f(m)$. Now replace $m$ by $m-1$, we then get $T(2^{m-1}) = f(m-1)$. $\endgroup$
    – user17762
    Jun 18 '12 at 1:41
  • $\begingroup$ 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? $\endgroup$
    – cody
    Jun 18 '12 at 2:01
  • $\begingroup$ ... and then prove by induction that the closed form is correct. $\endgroup$
    – Raphael
    Jun 18 '12 at 18:26
  • $\begingroup$ @cody Yes. and as Raphael points out use induction/recursion. $\endgroup$
    – user17762
    Jun 18 '12 at 18:28
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ You just wrote the formulas, how is this an answer? And this problem isn't satisfied by the master theorem, so that's wrong too. $\endgroup$
    – Mercury
    Oct 8 '20 at 16:29

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