Is log(n!) = Θ(n·log(n))?_问答_开发者_运维开发者技术经验分享

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

A hint was given that I should show the upper bound with n开发者_高级运维ⁿ and show the lower bound with (n/2)^(n/2). This does not seem all that intuitive to me. Why would that be the case? I can definitely see how to convert nⁿ to n·log(n) (i.e. log both sides of an equation), but that's kind of working backwards.

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

Remember that

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

You can get the upper bound by

log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)
                                = n*log(n)

And you can get the lower bound by doing a similar thing after throwing away the first half of the sum:

log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n) 
                                       = log(n/2) + log(n/2+1) + ... + log(n-1) + log(n)
                                       >= log(n/2) + ... + log(n/2)
                                        = n/2 * log(n/2)

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.

Is log(n!) = Θ(n·log(n))?

Sorry, I don't know how to use LaTeX syntax on stackoverflow..

See Stirling's Approximation:

ln(n!) = n*ln(n) - n + O(ln(n))

where the last 2 terms are less significant than the first one.

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)

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.

Thanks, I found your answers convincing but in my case, I must use the Θ properties:

log(n!) = Θ(n·log n) =>  log(n!) = O(n log n) and log(n!) = Ω(n log n)

to verify the problem I found this web, where you have all the process explained: http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm

http://en.wikipedia.org/wiki/Stirling%27s_approximation Stirling approximation might help you. It is really helpful in dealing with problems on factorials related to huge numbers of the order of 10^10 and above.

Is log(n!) = Θ(n·log(n))?

This might help:

e^ln(x) = x

and

(l^m)ⁿ = l^m*n

If you reframe the problem, you can solve this with calculus! This method was originally shown to me via Arthur Breitman https://twitter.com/ArthurB/status/1436023017725964290.

First, you take the integral of log(x) from 1 to n it is n*log(n) -n +1. This proves a tight upper bound since log is monotonic and for every point n, the integral from n to n+1 of log(n) > log(n) * 1. You can similarly craft the lower bound using log(x-1), as for every point n, 1*log(n) > the integral from x=n-1 to n of log(x). The integral of log(x) from 0 to n-1 is (n-1)*(log(n-1) -1), or n log(n-1) -n -log(n-1)+1.