3

I know that 

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

and 

 n*log(n)= log(n) + log(n) + .... + log(n) or just adding log(n)'s  n times.

What constant can I multiply n*log(n) that makes it smaller than log(n!)?

I read a few solutions about it being n/2*log(n/2). What constant is that? half?

One solution is from here. Is log(n!) = Θ(n·log(n))?

If C = 1/2, then isn't it just (n/2)*log(n)? How does the n inside of log get affected or why did n become n/2 all of a sudden?

I know the log rule of log(a/b) = log a - log b. Does that rule help?

Community
  • 1
  • 1
Arrow
  • 691
  • 2
  • 7
  • 15
  • 5
    This question appears to be off-topic because it belongs either on math.stackexchange.com or cs.stackexchange.com. – Barmar Feb 27 '14 at 10:20
  • 1
    There is a similar question to this that had a solution I didn't understand. I will edit my post to have the link. http://stackoverflow.com/questions/2095395/is-logn-nlogn – Arrow Feb 27 '14 at 10:25
  • I recently wrote up the simple estimate using Riemann sums and the trapezoid integration formula here: (http://math.stackexchange.com/questions/689752) – Lutz Lehmann Feb 27 '14 at 11:57

3 Answers3

3
log(n!) = log(1) + ... + log(n) >= log(n/2) + log(n/2+1) + ... + log(n)
>= n/2*log(n/2) = n/2 *log(n) - n/2*log(2) >= (*) n/2 log(n) - n/4 log(n) 
= n/4 log(n) = 1/4 nlog(n)

(*) is because for 'high enough' values of n (n>N for some constant N), n/2log(2) < n/4log(n), so we reduce 'bigger' element - which result in lower outcome.

So, we got that log(n!) >= 1/4*nlog(n) - which gives us that it is in Omega(nlogn) by definition with c=1/4.

Regarding the first part, how we got to log(n/2) + log(n/2+1) + ... +log(n)

log(1) + ... + log(n) >= log(1) + ... + log(n) - log(1) - log(2) - ... - log(n/2-1) = 
  = log(n/2) + log(n/2+1) + ... + log(n)
amit
  • 175,853
  • 27
  • 231
  • 333
  • Shouldn't the last inequality be in the other direction? I mean: `n/2 *log(n) - n/2*log(2) <= 1/2 * n*log(n)`. – Bolo Feb 27 '14 at 10:30
  • Hi amit, I was wondering if you can explain how you got log (n/2)+ log(n/2+1) + ... + log(n)? – Arrow Feb 27 '14 at 10:40
  • @MattC He just took the second half of the components. This means he threw away the first half, all of the components were non-negative. – Bolo Feb 27 '14 at 11:05
  • @Bolo Yea, you are right - did the needed changes, sorry for the mistake. – amit Feb 27 '14 at 11:06
  • @MattC See last part of the answer, added an explanation. – amit Feb 27 '14 at 11:07
  • @amit Sorry, that still doesn't make sense to me: `n/2 *log(n) - n/2*log(2) >= 1 * n*log(n)`. Let's say `A = n*log(n)` and `B = n/2*log(2)`. Note that `A > 0` and `B > 0`. Your last inequality says: `A/2 - B >= A`, which is clearly false. – Bolo Feb 27 '14 at 11:11
  • @Bolo Thanks for your patience. I messed up the constants, apologies. What do you think now? Thanks for your comments. – amit Feb 27 '14 at 11:17
  • @amit Now it's fine, +1. – Bolo Feb 27 '14 at 11:18
0

It is not a simple constant. I think you are considering the proof that O(log(n!)) = O(n*log(n)) and if that is the case, then you need to use Sterling's approximation. If you use this approximation you can show that for any value c < 1 there should be a value N such that for n >= N c * n*log(n) < log(n!).

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
  • 1
    (1)This question is about Omega, not big-O. (2) there is no need for the exact (tightest) constant, just need to show such a constant exist, which is fairly simple. – amit Feb 27 '14 at 10:23
  • @amit I saw that it is about omega but I thought we need the tightest. Maybe I misinterpret the question? – Ivaylo Strandjev Feb 27 '14 at 10:24
  • From my understanding of the question, @MattC wants to know how to prove that log(n!) is in Omega(nlogn), so you just need to show such a constant exists. – amit Feb 27 '14 at 10:25
  • I assume that there is a constant from this one thread (which I do not understand) http://stackoverflow.com/questions/2095395/is-logn-nlogn – Arrow Feb 27 '14 at 10:27
  • @MattC do you need *a* constant or as tight a constant as you can get. If you just need any amit's answer is perfect for you. If you need to get to tightest possible you'll need what I mention above. – Ivaylo Strandjev Feb 27 '14 at 10:28
  • amit's answer should be okay for me. I don't need it very tight. However, I'm having a little bit of trouble understanding it completely... – Arrow Feb 27 '14 at 10:37
0

To make the first answer by amit a little more elementary:

Consider n!=1*2*3*...*(n-1)*n combined with itself in reverse order, that is, as

   (n!)^2=(n)*(1*(n-1))*(2*(n-2))*...*((n-1)*1)*(n)

Then each of the inner products allows the following estimates

    k*(n-k)>=1*max(k,n-k)>=n/2

and by the arithmetic-geometric mean, or just the fact that x*(1-x) is largest in the middle of 0 and 1 at 1/2,

    k*(n-k)<=((n-k)+k)/2)^2=(n/2)^2

Combining everything we get

    n*(n/2)^(n-1)*n <= (n!)^2 <= n*(n/2)^(2(n-1))*n

and taking the logarithm and dividing by 2

    (n+1)/2*log(n/2)+log(2) 
         <= log(n!) 
             <= n*log(n/2)+log(2)

so that the lower bound has a leading term of 1/2*n*log(n) and the upper bound has a leading term of n*log(n).

Lutz Lehmann
  • 25,219
  • 2
  • 22
  • 51