2
$\begingroup$

Possible Duplicate:
$T(n) = 4T({n/2}) + \theta(n\log{n})$ using Master Theorem

What is the order of this recurrence?

$$T(n)=3T(n/2) + n\log n,\ \ T(1)=1$$

I found the answer where $a=2$ using the Master Theorem case 2, but was unable to make this work for $a=3$.

  • 0
    What is $a$? You've left something out.2012-02-07
  • 0
    usually, best to define $R(k) = T(2^k)$. Then $R(k)=3R(k-1) + k2^k\log 2$.2012-02-07

2 Answers 2