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.

  • $\begingroup$ can not seem to be able to solve it help help help :( $\endgroup$ – Bunny Rabbit Dec 28 '10 at 10:58
  • 2
    $\begingroup$ 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$ $\endgroup$ – Ross Millikan Dec 28 '10 at 14:06
  • $\begingroup$ 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 :( $\endgroup$ – Bunny Rabbit Dec 28 '10 at 14:28
  • 1
    $\begingroup$ @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. $\endgroup$ – 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.

  • $\begingroup$ 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$? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.