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

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! What is the closed form for T(n)?2012-02-07
  • 0
    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)$.2012-02-07
  • 0
    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.2012-02-07
  • 0
    I replied to this in my main answer above.2012-02-08
  • 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}}

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