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?
 A: 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.
A: 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.
A: 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.
