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}).$$
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.
