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}\]