# how to solve the recurrence $T(n) = 2T(n/3) + n\log n$

How do we solve the recurrence $T(n) = 2T(n/3) + n\log n$?

Also, is it possible to solve this recurrence by the Master method?

-

Hint: It is possible to solve by Master theorem.

A more generic method is Akra Bazzi, but you don't need that for this problem.

-
can not seem to be able to solve it help help help :( –  Bunny Rabbit Dec 28 '10 at 10:58
It looks to me like it fits Case 3 as shown on the Wikipedia page. $a=2, b=3, f(n)=n \log(n)=\Omega(n^{\log_3 (2)+\epsilon}),$ if you take $\epsilon = 0.4$, say. $2f(\frac{n}{3})=2\frac{n}{3}\log\frac{n}{3}\leq c f(n)$ for large $n$ if $.667\le c \le 1$ –  Ross Millikan Dec 28 '10 at 14:06
why are you taking $\epsilon =0.4$ , also the logic of c being greater thn .667 is not clear to me , sorry i am a noob :( –  Bunny Rabbit Dec 28 '10 at 14:28
@Bunny: Ross is right. Case 3 fits. I suggest you carefully read what case 3 assumes and at the same time read Ross' comment and try to see how it fits. –  Aryabhata Dec 28 '10 at 17:30

In order to apply the Master Theorem we define $a=2$, $b=3$ and $f\left(n\right)=n\lg n$

Since [ n^{log_{3}2+0.4}\approx n ] we have that $f\left(n\right)=\Omega\left(n^{log_{b}a+\epsilon}\right)$, where $\epsilon=0.4$ . The regularity condition on $f\left(n\right)$ will be verified if, for some $c<1$: $$2\frac{n}{3}\lg\left(n/3\right)\leq cn\lg(n)$$ Since it is clear that $$\left(\frac{2}{3}\right)n\left(\lg n-\lg3\right)<\left(\frac{2}{3}\right)n\lg(n)$$ the constant $c=\frac{2}{3}<1$ is such that the regularity condition is met for sufficiently large n. Thus, case 3 of the Master Theorem applies and $T\left(n\right)=\Theta\left(n\lg n\right)$, answering the question.

-
The last step seems strange. How did you get rid of the log on the left side, but not the right? Also, can't you just take $c=2/3$ when you have $2\log(n/3)/3 \leq c \log n$? –  Aryabhata Dec 29 '10 at 1:10

There is another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and $T(1)=T(2)=1$ and for $n\ge 3$ $$T(n) = 2 T(\lfloor n/3 \rfloor) + n \lfloor \log_3 n \rfloor.$$

Furthermore let the base three representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_3 n \rfloor} d_k 3^k.$$

Then we can unroll the recurrence to obtain the following exact formula for $n\ge 3$ $$T(n) = 2^{\lfloor \log_3 n \rfloor} + \sum_{j=0}^{\lfloor \log_3 n \rfloor -1} 2^j \times (\lfloor \log_3 n \rfloor - j) \times \sum_{k=j}^{\lfloor \log_3 n \rfloor} d_k 3^{k-j}.$$

Now to get an upper bound consider a string of two digits to obtain $$T(n) \le 2^{\lfloor \log_3 n \rfloor} + \sum_{j=0}^{\lfloor \log_3 n \rfloor -1} 2^j \times (\lfloor \log_3 n \rfloor - j) \times \sum_{k=j}^{\lfloor \log_3 n \rfloor} 2 \times 3^{k-j}.$$ This simplifies to $$(9 \lfloor \log_3 n \rfloor - 18) \times 3^{\lfloor \log_3 n \rfloor} + 17 \times 2^{\lfloor \log_3 n \rfloor} + \lfloor \log_3 n \rfloor + 2.$$

This bound is actually attained and cannot be improved upon, just like the lower bound, which occurs with a one digit followed by zeroes to give $$T(n) \ge 2^{\lfloor \log_3 n \rfloor} + \sum_{j=0}^{\lfloor \log_3 n \rfloor -1} 2^j \times (\lfloor \log_3 n \rfloor - j) \times 3^{\lfloor \log_3 n \rfloor-j}.$$ This simplifies to $$(3 \lfloor \log_3 n \rfloor - 6) \times 3^{\lfloor \log_3 n \rfloor} + 7 \times 2^{\lfloor \log_3 n \rfloor}.$$

Joining the dominant terms of the upper and the lower bound we obtain the asymptotics $$\lfloor \log_3 n \rfloor \times 3^{\lfloor \log_3 n \rfloor} \in \Theta\left(\log_3 n \times 3^{\log_3 n}\right) = \Theta\left(\log n \times n\right).$$

Observe that there is a lower order term $$2^{\lfloor \log_3 n \rfloor} \in \Theta\left(3^{\log_3 2 \times \log_3 n}\right) = \Theta\left(n^{\log_3 2}\right).$$

This term represents the asymptotics being generated by the recursive term in the recurrence.

These are both in agreement with what the Master theorem would produce.

This MSE link has a series of similar calculations.

-