0
$\begingroup$

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.

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

1 Answer 1

Reset to default
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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