For the computation of the log factorial, i.e., $\log(n!)$, is the Big(O) run time for this $n\log(n)$? How can this be assumed graphically?
***Update: How does the sum of $\log(n!)$ work then? I.e., the sum of log Factorial?
$\endgroup$ 32 Answers
$\begingroup$Notice that:
$$\log(ab)=\log(a)+\log(b)$$
Thus,
$$\log(n!)=\sum_{k=1}^n\log(k)<\sum_{k=1}^n\log(n)=n\log(n)$$
A lower bound may be done with Riemann sums:
$$\sum_{k=1}^n\log(k)>\int_1^n\log(x)\ dx=n\log(n)-n+1$$
Here's the graphical component:
$$\log(n!) = \sum_{k=1}^n \log(k)$$ Can you figure it out from here using properties of Big-$O$ notation? You'll find that the answer to your conjecture is a resounding yes; graphically, this is because $n^n$ is a decent estimator of $n! $. Look up Stirling Approximation for more detail
$\endgroup$ 10
