# Recurrence relations and the Master Theorem

Although it might be a bit of newbie question, my question is, How can I apply the Master theorem to the following relation:

T(n) = 99T(n/100) + log(n!)


I'm trying to learn about algorithms, but I'm not really comfortable with logarithms(haven't studied in school yet), so I'd really appreciate a bit of help. Thanks.

• Try using $\log (n!) = \Theta(n \log n)$. – Inuyasha Yagami Jan 30 at 16:53
• Thanks very much, but could please link to a proof of this? – kasra Jan 30 at 18:34
• en.wikipedia.org/wiki/Stirling%27s_approximation. You asked something similar a few days before also. :) – Inuyasha Yagami Jan 30 at 18:35
• yes, I'm really new to this stuff. Thanks very much :) – kasra Jan 30 at 18:39
• You can answer your own question if you have solved it. Just for the sake of completeness. – Inuyasha Yagami Feb 3 at 8:07

We know that $$n! \le n^n$$, therefore $$\log n! \le n \log n$$. Then $$T(n) \le 99T( \frac{n}{100} ) + n \log n$$
Let $$c=\log_{100} 99 < 1$$ and notice that $$n \log n$$ is polynomially larger than $$n^c$$. Indeed: $$n \log n \in \Omega(n) \subset \Omega(n^c).$$ By the master theorem we have $$T(n) = O(n \log n)$$.
This is tight because $$\Omega(n \log n)$$ is also a lower bound since: $$T(n) \ge \log n! \ge \log ( \lfloor n/2 \rfloor^{(n/2)} ) = (n/2) \log ( \lfloor n/2 \rfloor) = \Omega(n \log n).$$
To summarize, you have $$T(n) = \Theta(n \log n)$$.