I'm trying to find the tightest upper bound for runtime of a function whose recurrence relation is the following: $T(n) = 2T(n/4) + O(n^2 \log n)$
I got $O(n^2 \log n)$ but I'm not sure if that is correct. I arrived to the solution using the Advanced master theorem: https://www.geeksforgeeks.org/advanced-master-theorem-for-divide-and-conquer-recurrences/#
On
Considering the recurrence
$$ T(n) = 2 T\left(\frac n4\right)+k n^2\log_4n $$
making $n=4^m$ we have
$$ T\left(4^m\right)=2T\left(4^{m-1}\right)+k m 4^{2m} $$
This recurrence can be recast as
$$ R(m) = 2R(m-1)+k m 4^{2m} $$
This is a linear recurrence and can be solved as
$$ R(m) = R_h(m) + R_p(m),\ \ \ \cases{R_h(m) = 2R_h(m-1)\\ R_p(m) = 2R_p(m-1)+k m 4^{2m}} $$
The homogeneous has solution
$$ R_h(m) = c_02^m $$
now assuming $R_p(m) = c_0(m)2^m$ after substitution into the particular we have
$$ c_0(m)2^m = 2 c_0(m-1)2^{m-1}+k m 4^{2m} $$
or
$$ c_0(m) = c_0(m-1) + k m 2^{3m} $$
with solution
$$ c_0(m) = \frac{8}{49} k \left(2^{3m} (7 m-1)+1\right) $$
then
$$ R_p(m) = \frac{8}{49} k \left(2^{3m} (7 m-1)+1\right)2^m $$
and thus
$$ R(m) = \left(c_0+\frac{8}{49} k \left(2^{3m} (7 m-1)+1\right)\right)2^m $$
and now going backwards with $m = \log_4 n$ we obtain
$$ T(n) = \left(c_0\sqrt{n}+\frac{8}{49} k \left(n^2 \left(7\log_4 n-1\right)+\sqrt{n}\right)\right) = O\left(n^2\log_4 n\right) $$
One way to arrive at the desired bound is to expand the recurrence. We will compute the first few iterations and then generalise. The first one is:
$$T(n) = n^2 \lg n + 2T\left( \frac{n}{4} \right)$$
Then:
$$T(n) = n^2 \lg n + 2 \left( \frac{n}{4} \right)^2 \lg \frac{n}{4} + 2^2 T\left( \frac{n}{4^2} \right)$$
And after one more:
$$T(n) = n^2 \lg n + 2 \left( \frac{n}{4} \right)^2 \lg \frac{n}{4} + 2^2 \left( \frac{n}{4^2} \right)^2 \lg \frac{n}{4^2} + 2^3 T\left( \frac{n}{4^3} \right)$$
Now we generalise to:
$$T(n) = \sum_{i = 0}^{\frac{1}{2} \lg n} \frac{1}{8^i} n^2 \lg \frac{n}{4^i} + \sqrt{n} $$
$$= n^2 \lg n \sum_{i = 0}^{\frac{1}{2} \lg n} \frac{1}{8^i} - n^2 \sum_{i = 0}^{\frac{1}{2} \lg n} \frac{2i}{8^i} + \sqrt{n} $$
We can bound $T(n)$ from below:
$$T(n) \geq n^2 \lg n \sum_{i = 0}^{\frac{1}{2} \lg n} \frac{1}{8^i} - n^2 \sum_{i = 1}^{\frac{1}{2} \lg n} \frac{1}{4^i} + \sqrt{n}$$
And from above:
$$ T(n) \leq n^2 \lg n \sum_{i = 0}^{\frac{1}{2} \lg n} \frac{1}{8^i} + \sqrt{n} $$
The bound $\frac{1}{2} \lg n$ is the number of times $n$ needs to be divided by $4$ to reduce $n$ to $O(1)$, i.e. $n = 4^k = 2^{2k}$ and so $k = \frac{1}{2} \lg n$. Computing the geometric series gives:
$$ T(n) \geq \frac{8}{7} n^2 \lg n - \frac{1}{7} \sqrt{n} \lg n - \frac{1}{3} n^2 + \frac{1}{3} n + \sqrt{n}$$
$$T(n) \leq \frac{8}{7} n^2 \lg n - \frac{1}{7} \sqrt{n} \lg n + \sqrt{n}$$
And so we conclude $T(n) = O(n^2 \lg n)$, which we can verify using the substitution method. Removing lower order terms we assume $T(n) \leq c n^2 \lg n$. Now we substitute into the recurrence relation:
$$T(n) = 2T\left( \frac{n}{4} \right) + kn^2 \lg n $$ $$T(n) = 2\left( c \left( \frac{n}{4} \right)^2 \lg \frac{n}{4} \right) + kn^2 \lg n $$
$$T(n) = \frac{c}{8} n^2 \lg \frac{n}{4} + kn^2 \lg n$$ $$T(n) = \frac{c}{8} n^2 \lg n - \frac{c}{4} n^2 + kn^2 \lg n$$ $$T(n) = \left( \frac{c}{8} + k\right)n^2 \lg n - \frac{c}{4} n^2$$ $$T(n) \leq cn^2 \lg n$$
The last inequality holds for sufficiently large $c$, e.g. $\frac{8}{7} k \leq c$. Which shows that $T(n) = O(n^2 \lg n)$ as you thought. We could have also verified the bound by plugging the recurrence relation into a tool like Wolfram Alpha which gives the desired upper bound.