Big O notation on the log factorial

Question

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?

Answer 1

$$\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

Answer 2

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: