How to solve the following recurrence? $T(n) = 4T(\frac{n}{2})+n!$
"... the masters theorem would not work with the above equation" is not right. From the master theorem, as we know $n! = \Omega(n^3)$, and $4\left(\frac{n}{2}\right)! &lt; 0.9 n!$ ($k = 0.9$) for large enough $n$, so $T(n) = \Theta(n!)$.

To know more about this case, follow this link and find third case of the master theorem.