How do I get the solution for a recursion with n! using Master Theorem? The problem in my book is T(n) = 16T(n/4) + n!

I don't know how to get at the correct solution my book has, which says Θ(n!)

here are pictures of the master theorem and the problem in my book.
Suppose for simplicity that we only consider $n = 4^k$, and that $T(1) = 1$.

Let us guess that $T(n) \leq Cn!$ (where $C&gt;0$), and try to prove it by induction. For the inductive step we need
$$
16C(n/4)! + n! \leq Cn!,
$$
that is,
$$
16C(n/4)! \leq (C-1)n!.
$$
For the base case we need $C \geq 1$.

Let us write the inductive constraint for $n = 4$:
$$
16C \leq 24(C-1) \Longrightarrow C \geq 3.
$$
This prompts us to choose $C = 3$. For $n \geq 4$ we then need
$$
48 (n/4)! \leq 2n! \Longleftrightarrow \frac{n!}{(n/4)!} \geq 24.
$$
It is easy to check that this always holds – for $n = 16$ it's a simple computation, and for $n \geq 64$ we have $n!/(n/4)! \geq n &gt; 24$.



Intuitively, what is happening here is that $(n/4)!$ is much much smaller than $n!$, and so $T(n) \approx n!$, since all other summands (which you see if you unroll the recursion) are so much smaller.