# Solving a recurrence relation using Divide and Conquer Master Theorem [duplicate]

For the recurrence relation

$$T(n) = 16T(n/4) + n!\,,$$

I have found that $T(n)\in Θ(n!)$. Can this be deduced using the Master Theorem?

## marked as duplicate by Raphael♦Jan 16 '15 at 11:19

Yes. Recall that the Master Theorem deals with recurrences of the form $$T(n) = a\cdot T\left(\frac{n}{b}\right)+f(n)$$ In your particular case you have $a = 16$, $b=4$ and $f(n) = n!$.
Then we decide the complexity by comparing $f(n)$ to three functions of $n$, $a$ and $b$ (really we compare it basically the same function, with a $\log$ wiggle room, but in different ways).
In particular the third case holds where $f(n) \in \Omega(n^{c})$ where $c > \log_{b}a$. You have that $\log_{b}a = \log_{4}16 = 2$, so you have to prove (or at least convince yourself, depending on how rigorous you're being) that $n! \in \Omega(n^{c})$ for some $c > 2$.
It should be reasonably clear that you can pick any constant $c$ in this instance, and that this case holds. As it does, we get immediately (which is of course the point of the Master Theorem) that $T(n) \in \Theta(f(n))$, which in this case gives $T(n) \in \Theta(n!)$.