Is the Summation of lg k in log(n!) Equal to Theta (n lgn)?

MzLeeTooFresh
Messages
3
Reaction score
0

Homework Statement


Prove that the following is true:
n
\Sigma lg k = \Theta (n lgn)
k=1

Homework Equations



the lg in this case is base 2

The Attempt at a Solution


i don't kno how to apply geometric or arithmetic progression to the 1st part
i was trying to substitute for k but that wasnt working out.
i'm not looking for the answer but for some guidance as to how to deal with the summation
 
Last edited:
Physics news on Phys.org
it helps a lot to know that log(a)+ log(b)= log(ab)!

There is NO artihmetic or geometric progression here.
 
Sum(lg k) = lg (n!)

we have n! < nn therefore

Sum(lg k) = lg (n!) < lg (nn) = nlg(n)
 
so it would then be:
n
lg \Pi k
k=1
?
 
yes, just like HallsofIvy suggested lg 1 + lg 2 + ... + lg (n) = lg 1*2*3...*n = lg (n!)
 
ok thank you
 
MzLeeTooFresh said:
ok thank you

Two things, another, equivelant way to look at it is this:

The biggest term in: Sum(log k) is log n, since there are n terms, sum(log k) < n log n

Second, all you have shown is that sum(log k) = O(n log n), but you need to show it is BigTheta.
 
That is, you need to find an absolute constant K and an N(K) such that if n > N(K) then K n log n < log(n!).
 
Back
Top