$T(n)=3T(n/2) + n\log n,\  T(1)=1$ 
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$.
 A: You need to use Case 1 of the master theorem, which says that if
$$
T(n)=aT(n/b)+f(n),\qquad a\ge 1, \ b>1, \qquad (1)$$
and
$$f(n)=O(n^{(\log_b a)-\epsilon}), \qquad \epsilon>0,\qquad (2)$$
then $$T(n)=\Theta(n^{\log_b a}). \qquad (3)$$
(Also, some assumptions on the way to round $n/b$ and the positivity of $T$ and $f$ are necessary.)
In this case, $a=3$ and $b=2$, so $\log_b a =\log_2 3 > 1$.  Since $f(n)=n\log n$, we have $f(n)=O(n^{1+\delta})$ for any $\delta>0$.  Now take $\delta=\epsilon=((\log_b a)-1)/2$ to find that (2) holds.  Then. by (3), $T(n)=\Theta(n^{\log_2 3}).$
To find the order of $T(n)$ without using the master theorem, you can do the following:


*

*Find a constant $\epsilon>0$ such that, if $2^m\le n\le 2^{m+1}$ and $m\ge 0$, then $T(n)\ge \epsilon 3^m$.  Then prove by induction that this is true for all $m\ge 0$.  This proves that $T(n)=\Omega(n^{\log_2 3}).$

*Find constants $K>0$, $L>0$, and $M\ge 0$ such that, if $2^m\le n\le 2^{m+1}$ and $m\ge M$, then $T(n)\le K 3^m - L m 2^m $.  Then prove by induction that this is true for all $m\ge M$.  This proves that $T(n)=O(n^{\log_2 3}).$
Together, this proves that $T(n)=\Theta(n^{\log_2 3}).$
A: Let $R(k)=T(2^k)$.  Then $R(k)=3R(k-1)+k2^k\log 2$. So $$R(k)=3^{k-1} + \sum_{i=2}^{k} 3^{k-i}i2^i\log 2 = 3^{k-1} + 3^k\log 2\sum_{i=2}^k i\left(\frac 2 3\right)^i$$.
Since $\sum_{i=2}^\infty i\left(\frac 2 3\right)^i$ converges, $R(k)$ is essentially exponential with base $3$.  
Now use that $T(n)=R(\log_2 n)$.
So, there are $c_0,c_1$ such that for $n>4$, $$c_0 3^{\log_2{n}}<T(n) < c_1 3^{\log_2 n} $$.  Writing $3=2^{\log_3{2}}$, we can see that:
$$c_0n^{\log_3 2}< T(n) < c_1n^{\log_3 2}$$
