$T(n) = 4T(n/3) + n\log_3(n)$ using Mater Theorem? I am trying to solve this recurrence using the Master Theorem.
$$T(n)=4T(n/3)+n\log_3n.$$
I tried this:
We have: $a=4$, $b=3$ and $f(n)=n\log_3n$.
I think that  $f(n)$ is $O(n^{\log_ba - \epsilon})$ but I cannot prove it.
Find $c>0$ and $n_0>0$ such that: $\forall\,n\geqslant n_0$, $n\log_3n\leqslant c\cdot n^{\log_34+\epsilon}$  ?
So I claim that $$f(n) = \Theta(n^{\log_34}).$$
 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) = 4 T(\lfloor n/3 \rfloor) + n \lfloor \log_3 n \rfloor.$$
It seems reasonable to use integer  values here as the running time of
an algorithm is a function of discrete quantities.
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) = 4^{\lfloor \log_3 n \rfloor}
+ \sum_{j=0}^{\lfloor \log_3 n \rfloor -1} 
4^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  value two digits to
obtain
$$T(n) \le 4^{\lfloor \log_3 n \rfloor}
+ \sum_{j=0}^{\lfloor \log_3 n \rfloor -1} 
4^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
$$\frac{329}{9} \times 
4^{\lfloor \log_3 n \rfloor}
- (9 \lfloor \log_3 n \rfloor + 36) \times 3^{\lfloor \log_3 n \rfloor}
+ \frac{1}{3} \lfloor \log_3 n \rfloor + \frac{4}{9}.$$
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 4^{\lfloor \log_3 n \rfloor}
+ \sum_{j=0}^{\lfloor \log_3 n \rfloor -1} 
4^j \times (\lfloor \log_3 n \rfloor - j) \times 
3^{\lfloor \log_3 n \rfloor-j}.$$
This simplifies to
$$ 13 \times 4^{\lfloor \log_3 n \rfloor}
- (3\lfloor \log_3 n \rfloor + 12) 
\times 3^{\lfloor \log_3 n \rfloor}.$$
Joining the dominant terms of the upper and the lower bound we obtain
the asymptotics
$$4^{\lfloor \log_3 n \rfloor}
\in \Theta\left(4^{\log_3 n}\right) 
= \Theta\left(3^{\log_3 4 \times \log_3 n}\right) 
= \Theta\left(n^{\log_3 4}\right).$$
This is in agreement with what the Master theorem would produce.
