The problem is to solve this using Master Theorem :

$ $ T(n) = 16T(n/2)+[n\log_2 {n}]^4$ $

My attempt: I said that master theorem does not apply because the ratio of $ f/g = [\log_2 {n}]^4$ . This has no polynomial factor. But, when I looked at similar problems online, I saw some people apply case #2 here.

The version of the Master Theorem we use is as follows:

Our book also notes that in the first case not only must $ f$ be smaller than $ n^{\log_b{a}}$ , it must *polynomially smaller*, that is, $ f$ must be asymptotically smaller than $ n^{\log_b{a}}$ by a factor of $ n^\varepsilon$ for some constant $ \varepsilon>0$ . Similarly, in the third case, not only must $ f$ be larger than $ n^{\log_b{a}}$ , it must *polynomially larger*.