# [algorithm] Is log(n!) = Θ(n·log(n))?

I realize this is a very old question with an accepted answer, but none of these answers actually use the approach suggested by the hint.

It is a pretty simple argument:

`n!`

(= 1*2*3*...*n) is a product of `n`

numbers each less than or equal to `n`

. Therefore it is less than the product of `n`

numbers all equal to `n`

; i.e., `n^n`

.

Half of the numbers -- i.e. `n/2`

of them -- in the `n!`

product are greater than or equal to `n/2`

. Therefore their product is greater than the product of `n/2`

numbers all equal to `n/2`

; i.e. `(n/2)^(n/2)`

.

Take logs throughout to establish the result.

I am to show that **log( n!) = Θ(n·log(n))**.

A hint was given that I should show the upper bound with ** n^{n}** and show the lower bound with

**(**. This does not seem all that intuitive to me. Why would that be the case? I can definitely see how to convert

*n*/2)^{(n/2)}**to**

*n*^{n}**(i.e. log both sides of an equation), but that's kind of working backwards.**

*n*·log(*n*)What would be the correct approach to tackle this problem? Should I draw the recursion tree? There is nothing recursive about this, so that doesn't seem like a likely approach..

This might help:

e^{ln(x)}= x

and

(l^{m})^{n}= l^{m*n}

Helping you further, where Mick Sharpe left you:

It's deriveration is quite simple: see http://en.wikipedia.org/wiki/Logarithm -> Group Theory

log(n!) = log(n * (n-1) * (n-2) * ... * 2 * 1) = log(n) + log(n-1) + ... + log(2) + log(1)

Think of n as *infinitly big*. What is infinite minus one? or minus two? etc.

log(inf) + log(inf) + log(inf) + ... = inf * log(inf)

And then think of *inf* as n.

For lower bound,

```
lg(n!) = lg(n)+lg(n-1)+...+lg(n/2)+...+lg2+lg1
>= lg(n/2)+lg(n/2)+...+lg(n/2)+ ((n-1)/2) lg 2 (leave last term lg1(=0); replace first n/2 terms as lg(n/2); replace last (n-1)/2 terms as lg2 which will make cancellation easier later)
= n/2 lg(n/2) + (n/2) lg 2 - 1/2 lg 2
= n/2 lg n - (n/2)(lg 2) + n/2 - 1/2
= n/2 lg n - 1/2
```

lg(n!) >= (1/2) (n lg n - 1)

Combining both bounds :

1/2 (n lg n - 1) <= lg(n!) <= n lg n

By choosing lower bound constant greater than (1/2) we can compensate for -1 inside the bracket.

Thus lg(n!) = Theta(n lg n)