I'm trying to figure out the order of growth of the recurrence as follows, assuming $T(1) = 1$:
\begin{align*} 4T(n/4) + n \log n^3 & = 4T(n/4) + 3n \log n\\ &=4^kT(n/4^k) + \sum_{j=0}^{k-1} (3/4^j) n \log (n/4^j) \end{align*}
Where the logs are base $4$.
Letting $k = \log_4 n$:
$$ =nT(1) + \sum_{j=0}^{\log_4 n-1} (3/4^j) n \log (n/4^j) $$
Now I guess I took the easy way out and write:
\begin{align*} &= n + \sum_{j=0}^{\log_4 n-1} (3/4^j) n \log (n/4^j) \\ &\le n + \sum_{j=0}^{\log_4 n-1} 3 n \log (n) \\ &= n + \log n [3 n \log (n)] \\ &= n + 3n\log^2n \\ &= O(n \log^2 n) \end{align*}
but I am wondering if this bound can be made tighter, or if there is a good way of telling when such comparisons can be made.
update If I don't make that assumption and instead write:
\begin{align*} n + \sum_{j=0}^{\log_4 n-1} (3/4^j) n \log (n/4^j) &= n + 3n \bigg [ \log n \sum_{j=0}^{\log_4 n-1} \frac{1}{4^j} - \log 4\sum_{j=0}^{\log_4 n-1}\frac{j}{4^j} \bigg ] \\ & = n + 3n [ \log n O(n) - \log 4 O(\log n)]\\ &= O(n \log n) \end{align*}