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.

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

  • $\begingroup$ Thanks a lot, I tried to answer it myself but my answer was wrong so I deleted it. Thank you. $\endgroup$ – kasra Feb 5 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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