There are at least two methods to solve this problem.
We first present the Akra-Bazzi theorem:
If the recurrence is of the form
$$T(x) = g(x) + \sum_{i = 1}^{k} a_i T(b_i x + h_i(x))$$
for all $x > x_0$ with the following conditions
- sufficient base cases
- $a_i > 0$ and $0 < b_i < 1$
- $|g(x)| \in O(x^c)$
- $|h_i(x)| \in O\left(\frac{x}{(\log x)^2}\right)$
Then
$$T \in \Theta\left(x^p \left(1 + \int_{1}^{x} \frac{g(u)}{u^{p + 1}}\right)\right)$$
where $p$ is the solution to the equation $$\sum_{i = 1}^{k} a_i b_i^p = 1$$.
Solution 0:
We simply apply the theorem.
Note $k = 1$, $g(x) = x \log x$, $a_1 = 1$, $b_1 = \frac{1}{4}$ and $h_1(x) = 0$.
Clearly they satisfy the assumptions, so we now solve the equation
$$\sum_{i = 1}^{1} a_i b_i^p = 1$$
$$\iff a_1 b_1^p = 1$$
$$\iff \left(\frac{1}{4}\right)^p = 1$$
$$\iff p = 0$$
Now proceed to solve the integral
$$\int_{1}^{x} \frac{u \log u}{u^{0 + 1}} = \int_{1}^{x} \log u = [u \log u - u]_1^x = x \log x - x + 1$$
So we have
$$T \in \Theta(x^0 (1 + x \log x - x + 1)) = \Theta(x \log x)$$
Solution 1:
Our plan is to express the recurrence in the form of sum, bound it by integrals and hope that the lower bound is $\Theta(n \log n)$ while the upper bound is $O(n \log n)$.
First, we put $n = 4^k$ and obtain
$$T(4^k) = 3^1 T(4^{k - 1}) + 3^0 4^k \log 4^k$$
$$= 3^2 T(4^{k - 2}) + 3^1 4^{k - 1} \log 4^{k - 1} + 3^0 4^k \log 4^k$$
$$= 3^3 T(4^{k - 3}) + 3^2 4^{k - 2} \log 4^{k - 2} + 3^1 4^{k - 1} \log 4^{k - 1} + 3^0 4^k \log 4^k$$
$$\vdots$$
$$= 3^k 4^0 T(1) + 3^{k - 1} 4^1 \log 4^1 + 3^{k - 2} 4^2 \log 4^2 + \dots + 3^1 4^{k - 1} \log 4^{k - 1} + 3^0 4^k \log 4^k$$
$$= 3^k \left(T(1) + \sum_{j = 1}^{k} \left(\frac{4}{3}\right)^j \log 4^j \right)$$
$$= 3^k \left(T(1) + \log 4 \sum_{j = 1}^{k} j \left(\frac{4}{3}\right)^j\right)$$
Now we can bound the sum by integrals since the function is monotone increasing
$$\int_{0}^{k} x \left(\frac{4}{3}\right)^x \le \sum_{j = 1}^{k} j \left(\frac{4}{3}\right)^j \le \int_{1}^{k + 1} x \left(\frac{4}{3}\right)^x$$
Put $a = \frac{4}{3}$
Note $$x a^x = x e^{x \log a}$$
Next we evaluate the integral using integration by parts
$$\int x a^x = \int x e^{x \log a} = \frac{1}{\log a} \left(x e^{x \log a} - \int e^{x \log a}\right)$$
$$= \frac{1}{\log a} \left(x e^{x \log a} - \frac{1}{\log a} e^{x \log a}\right) + C = \frac{a^x}{\log a} \left(x - \frac{1}{\log a} \right) + C$$
So
$$\int_{0}^{k} x \left(\frac{4}{3}\right)^x = \left[\frac{a^x}{\log a} \left(x - \frac{1}{\log a} \right) \right]_{0}^{k} = \frac{a^k}{\log a} \left(k - \frac{1}{\log a} \right) + \frac{1}{(\log a)^2} \in \Omega(k a^k)$$
and
$$\int_{1}^{k + 1} x \left(\frac{4}{3}\right)^x = \left[\frac{a^x}{\log a} \left(x - \frac{1}{\log a} \right) \right]_{1}^{k + 1} = \frac{a^{k + 1}}{\log a} \left(k + 1 - \frac{1}{\log a} \right) - \frac{a}{\log a} \left(1 - \frac{1}{\log a} \right) \in O(k a^k)$$
So one concludes
$$\sum_{j = 1}^{k} j \left(\frac{4}{3}\right)^j \in \Theta(k a^k)$$
Finally, assuming $T(1) \in \Theta(1)$, one has
$$T(n) = 3^k \left(T(1) + \log 4 \sum_{j = 1}^{k} j \left(\frac{4}{3}\right)^j\right)$$
$$\in \Theta(3^k) \Theta(k a^k) = \Theta \left(3^k k \left(\frac{4}{3}\right)^k\right) = \Theta(k 4^k) = \Theta(n \log_4 n) = \Theta(n \log n)$$
