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

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

  • 0
    thank you for all the help2012-02-14
1

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}}. Writing $3=2^{\log_3{2}}$, we can see that:

$c_0n^{\log_3 2}< T(n) < c_1n^{\log_3 2}$