log(n!) = Theta(nlogn)

+3 votes
How to explain this equation?  It seems to be clear that log(n!) = O(n log n), since log (1.2.3.4.5....n) <= log (n.n.n.n...n)    (n times).

However, how do we prove that log (n!) = Omega (n log n)
asked May 9 in Asymptotic Analysis by shakexin (180 points)
edited Jun 3 by Amrinder Arora

1 Answer

+1 vote
 
Best answer
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)
                                        = n/2 * log(n/2)
answered Jun 15 by Chris AlgoStar (408 points)
selected Jul 18 by Amrinder Arora
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...