Question

Can the Master theorem be applied to the recurrence T(n) = 4T( n/2 ) + n^2 lg_2(n)? Answer Yes or No, and explain your reasons carefully. Whichever way you answer, give an asymptotic upper bound for T(n). If this cannot be solved by the Master Theorem (which gives tight bounds), then consider a new recurrence T 0 (n) that is strictly greater than T(n) for sufficiently large n and that is “easily” solved using the Master Theorem

Answer 1

Master theorem can be applied to equations of the form given as:

Clearly, the given equation T(n) = 4T( n/2 ) + n^2 lg_2(n) is in the form expected by the Master Theorem where

a = 4, b = 2, k = 2 and p = 1

Clearly, a = b^k and p > -1. Hence,

T(n) = Θ(n^log₂4 log¹⁺¹n) = Θ(n² log²n)