Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

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.

share|improve this answer
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
add comment

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.

share|improve this answer
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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