# $T(n)=3T(n/2) + n\log n,\ T(1)=1$ [duplicate]

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

-

## marked as duplicate by JavaMan, Did, Gerry Myerson, Asaf Karagila, t.b.Feb 8 '12 at 15:33

What is $a$? You've left something out. – Thomas Andrews Feb 7 '12 at 18:15
usually, best to define $R(k) = T(2^k)$. Then $R(k)=3R(k-1) + k2^k\log 2$. – Thomas Andrews Feb 7 '12 at 18:16

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}$$

-

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

-
Thank you! What is the closed form for T(n)? – Jessie Feb 7 '12 at 19:51
Most likely, $T(n)$ does not have a simple closed form. With more work, you could get a more accurate asymptotic estimate for $T(n)$. – David Moews Feb 7 '12 at 20:06
Thank you again. The problem was "give the order without using the Master Theorem" and I thought I could get there if I could find a closed form (using the theorem), and prove it with induction as if I had guessed it. I also tried substitution. What should I have done? Thanks very much for your help. – Jessie Feb 7 '12 at 20:12
I replied to this in my main answer above. – David Moews Feb 8 '12 at 2:50
thank you for all the help – Jessie Feb 14 '12 at 1:31