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 polynomially 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:

\begin {aligned} T(n) & = \sum_{i = 0}^{\lg n} 4^i \cdot c\left(\left(\frac n {2^i} \right)^2 \cdot \lg \frac n {2^i} \right) \\ & = \sum_{i = 0}^{\lg n} 4^i \cdot c\left(\frac {n^2 (\lg n - \lg 2^i)} {2^{2i}} \right) \\ & = cn^2 \sum_{i = 0}^{\lg n} (\lg n - \lg 2^i) \\ & = cn^2 \left(\sum_{i = 0}^{\lg n} \lg n - \sum_{i = 0}^{\lg n} \lg 2^i\right) \\ & = cn^2 \left(\sum_{i = 0}^{\lg n} \lg n - \sum_{i = 0}^{\lg n} i\right) \\ & = cn^2 \left(\lg n \cdot \lg n - \frac {\lg n (\lg n + 1)} 2 \right) \\ & = cn^2 \left(\frac {(\lg n)^2} 2 - \frac {\lg n} 2 \right) \\ & = cn^2 \cdot \frac {(\lg n)^2} 2 - cn^2 \cdot \frac {\lg n} 2 \\ & \le cn^2 \cdot \frac {(\lg n)^2} 2 \\ & \le cn^2 \lg^2 n \end {aligned}