To prove lg n! = theta(n lg n) [closed]

Tag: algorithm Author: sadie8910 Date: 2011-09-01

I was trying to prove lg n! = theta(n lg n)

I used the below expression to prove it

0 <= c1(n lg n) <= lg n! <= c2(n lg n) - equation 1

By using lg n! <= c2(n lg n) from the above equation, I could prove that lg n! = big O(n lg n)

however to prove lg n! = big omega(n lg n), I need to use the other part of equation 1 which is

c1(n lg n) <= lg n! - equation 2

can anyone help me as to how to solve equation 2 to prove big omega. The hint which I got to know is to do perform integration. But I'm not able to do it. Kindly help me out here

Thank you very much.

I suggest you try your luck here:
n! = prod{i=1..n}(i) so lg n! = sum{i=1..n} lg(i) which you could "approximate" by the integral of lg(i).