How do I get the solution for a recursion with n! using Master Theorem?
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.