Is lower bound for log (n!) also nlogn

Question

I saw the same question here.They have proved the lower bound like this

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

My doubt is why can't the lower bound be n log n itself? Or is there any other tighter lower bound possible?. Why is it specifically n/2 * log(n/2)?

`O(N/2 . log(N/2) == O(N log N)`; constants like 2 don't count. It's why the base of the logarithms doesn't matter either. — Jonathan Leffler, Sep 10 '14 at 00:35

score 4 · Answer 1 · edited May 23 '17 at 12:29

This is used to prove that

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

To prove this it is enough to find both an upper bound and a lower bound of Θ(n·log(n))

The lower bound

n/2 * log(n/2)

already corresponds to Θ(n·log(n)). It is easy to obtain and belongs to the Θ we are interested in. Finding a tighter lower bound would be more difficult an is not necessary.

The complete proof in this question:

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

Is lower bound for log (n!) also nlogn

1 Answers1