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

Question

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?

Answer 1

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.

Answer 2

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.