Can the master method be applied to the recurrence $T(n) = 4T(n/2) + n^2 \lg n$? Why or why not? Give an asymptotic upper bound for this recurrence.

In the given recurrence, $a = 4$ and $b = 2$. Hence, $n^{\log_b a} = n^{\log_2 4} = n^2$ and $f(n) = \Theta(n^2 \lg n)$.

Now, asymptotically $f(n) = n^2 \lg n$ is definitely larger than $n^2$, but it is not polynomically larger than $n^2$. So, we cannot apply master method to this recurrence.

We can use recursion tree to get a good estimate of the asymptotic upper bound of the given reference and then use substitution method to prove that.

Rate of increase in number of subproblems in each recursion = 4 Rate of decrease in subproblem size = 2

Hence in each level of the tree, there are $4^i$ nodes each of cost $c((n/2^i)^2 \cdot \lg (n/2^i))$ at depth $i = 0, 1, 2, \dots, \lg n$.

Hence, total cost of the tree is: