0
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

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!)$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.