272

I am to show that log(n!) = Θ(n·log(n)).

A hint was given that I should show the upper bound with nn and show the lower bound with (n/2)(n/2). This does not seem all that intuitive to me. Why would that be the case? I can definitely see how to convert nn to n·log(n) (i.e. log both sides of an equation), but that's kind of working backwards.

What would be the correct approach to tackle this problem? Should I draw the recursion tree? There is nothing recursive about this, so that doesn't seem like a likely approach..

4
  • 2
    You should really write it including the "as n -> ∞ "
    – MartW
    Jan 19, 2010 at 18:49
  • 2
    Fun exercise: use the similar trick to show that the harmonic series 1/1 + 1/2 + 1/3 + 1/4 + ... diverges to infinity.
    – Yoo
    Jan 19, 2010 at 22:54
  • 15
    Shouldn't this be at cs.stackexchange.com? Jan 17, 2013 at 20:25
  • 11
    @CodyBugstein, cs.stackexchange.com didn't exist back when the question was asked
    – MrMartin
    Jun 20, 2019 at 9:40

10 Answers 10

393

Remember that

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+1) + ... + log(n-1) + log(n)
                                       >= log(n/2) + ... + log(n/2)
                                        = n/2 * log(n/2) 
7
  • 7
    This is a very nice proof for the upper bound: log(n!) = log(1) + ... + log(n) <= n log(n) => log(n!) = O(n log n). However, for proving the lower bound (and consequently big-tetha), you'll probably need Stirling's Approximation. Jan 19, 2010 at 20:34
  • 40
    You don't need Sterling's approximation for a lower bound. log(n!) = log(1) + ... + log(n) >= log(n/2) + ... + log(n) >= n/2 * log(n/2) = Omega(n log n). Jan 19, 2010 at 22:40
  • 2
    @Keith: I don't get it yet. Could you (or someone) expand a few more terms for me in the "..." part of "log(n/2) + ... + log(n)" please? Thanks! Jan 21, 2010 at 9:31
  • 6
    @j_random_hacker: log(n/2) + log(n/2 + 1) + ... + log(n - 1) + log(n) (larger half of the terms of log(n!)). Actually, I just read the question and saw that the clue is stated in the question. Basically, (n/2)^(n/2) <= n! <= n^n => log((n/2)^(n/2))<=log(n!)<=log(n^n) => Θ(n/2 * log(n/2))<=log(n!)<=Θ(n*log(n)) Jan 21, 2010 at 14:07
  • 6
    this explanation is similar to accepted answer, but has a bit more details: mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm
    – gayavat
    Oct 2, 2015 at 8:15
51

I realize this is a very old question with an accepted answer, but none of these answers actually use the approach suggested by the hint.

It is a pretty simple argument:

n! (= 1*2*3*...*n) is a product of n numbers each less than or equal to n. Therefore it is less than the product of n numbers all equal to n; i.e., n^n.

Half of the numbers -- i.e. n/2 of them -- in the n! product are greater than or equal to n/2. Therefore their product is greater than the product of n/2 numbers all equal to n/2; i.e. (n/2)^(n/2).

Take logs throughout to establish the result.

3
  • 12
    This is actually just the same as the log version in the accepted answer but taking the logarithm after instead of before. (it more clearly uses the hint though)
    – hugomg
    Nov 3, 2011 at 4:21
  • How’s this different to the accepted answer?
    – Harsh
    Sep 14, 2021 at 6:07
  • @Harsh Check the edit history on the accepted answer and compare the timestamps to this answer.
    – Nemo
    Sep 24, 2021 at 17:49
32

enter image description here

Sorry, I don't know how to use LaTeX syntax on stackoverflow..

7
  • 3
    This is a great explanation! I could follow this until step 7, but then I cannot decode the mathemagic that happens between step 7 and step 8... :-(
    – Oliver
    Oct 31, 2019 at 16:15
  • 6
    @Z3d4s The argument in step 7 is basically, that the first term on the right hand side is the dominant term and that log(n!) can therefore approximated by nlog(n) or that it is of order nlog(n) which is expressed by the big O notation O(n*log(n)).
    – Gilfoyle
    Oct 31, 2019 at 18:44
  • 1
    @Z3d4s the what steps 7-8 conversion is saying that nlogn == log(n^n) and for showing the bound here you can say the first term is always greater than the second term you can check for any larger values, and for expressing big-O complexity we will always take the dominating item of all. So nlogn contributes to the big-O time. Apr 18, 2020 at 13:18
  • 2
    @rsonx It's both - see the accepted answer, for example. Regarding the {some positive but non-dominating term} - actually all the elements of multiplication are < 1, therefore the product is < 1 as well. log brings it to negative values so the asymptotic result here is actually O(nlogn) - {something}. It remains to be proved if that something is insignificant asymptotically compared to nlogn - and this answer doesn't provide it. It doesn't affect the big-O but can affect the Omega. Anyway, this is overcomplication, see other answers Nov 12, 2020 at 0:58
  • 2
    @Z3d4s Basically for n -> ∞ , (1/n) -> 0. Hence (1 - (k/n)) -> 1. thus log of the product term would tend towards 0 Dec 25, 2021 at 16:07
15

See Stirling's Approximation:

ln(n!) = n*ln(n) - n + O(ln(n))

where the last 2 terms are less significant than the first one.

0
10

For lower bound,

lg(n!) = lg(n)+lg(n-1)+...+lg(n/2)+...+lg2+lg1
       >= lg(n/2)+lg(n/2)+...+lg(n/2)+ ((n-1)/2) lg 2 (leave last term lg1(=0); replace first n/2 terms as lg(n/2); replace last (n-1)/2 terms as lg2 which will make cancellation easier later)
       = n/2 lg(n/2) + (n/2) lg 2 - 1/2 lg 2
       = n/2 lg n - (n/2)(lg 2) + n/2 - 1/2
       = n/2 lg n - 1/2

lg(n!) >= (1/2) (n lg n - 1)

Combining both bounds :

1/2 (n lg n - 1) <= lg(n!) <= n lg n

By choosing lower bound constant greater than (1/2) we can compensate for -1 inside the bracket.

Thus lg(n!) = Theta(n lg n)

2
  • 2
    This extended derivation is needed because, "something" >= n/2 * lg(n/2) is not equal to omega(n lg n) which was mentioned in one of the previous comment. Feb 21, 2015 at 3:13
  • This should read "a constant SMALLER than (1/2)" as we are trying to find a lower bound. Any constant, c, smaller than (1/2) will eventually make cnlogn <= (1/2)n*logn-(1/2)n, for a large enough n.
    – Matthew
    Aug 14, 2019 at 4:08
4

Thanks, I found your answers convincing but in my case, I must use the Θ properties:

log(n!) = Θ(n·log n) =>  log(n!) = O(n log n) and log(n!) = Ω(n log n)

to verify the problem I found this web, where you have all the process explained: http://www.mcs.sdsmt.edu/ecorwin/cs372/handouts/theta_n_factorial.htm

3

Helping you further, where Mick Sharpe left you:

It's deriveration is quite simple: see http://en.wikipedia.org/wiki/Logarithm -> Group Theory

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

Think of n as infinitly big. What is infinite minus one? or minus two? etc.

log(inf) + log(inf) + log(inf) + ... = inf * log(inf)

And then think of inf as n.

1
  • I disagree with this, because by this logic the argument could be made that n = O(n!) as such. As per your claim, log(n!) = inf * log(inf). "Think of n as infinitely big". What is log(infinity)? Infinity. Therefore, inf * log(inf) is infinity. from the other side, n is the square root of n, times itself. as n gets infinitely large, the square root does too, so you get infinity * infinity, which also equals infinity. Infinity = Infinity: Q.E.D. Jul 1 at 19:50
2

http://en.wikipedia.org/wiki/Stirling%27s_approximation Stirling approximation might help you. It is really helpful in dealing with problems on factorials related to huge numbers of the order of 10^10 and above.

enter image description here

1

This might help:

eln(x) = x

and

(lm)n = lm*n
4
  • 4
    Actually, that's wrong: 1^(m^n) != 1^(mn) it must be (1^m)^n = 1^(mn)
    – Pindatjuh
    Jan 19, 2010 at 18:18
  • Errr I mean L instead of 1 in the above comment.
    – Pindatjuh
    Jan 19, 2010 at 18:35
  • He didn't write 1^(m^n) he wrote (l^m)^n Jan 17, 2013 at 20:57
  • 3
    @CodyBugstein: There was an edit made to fix the problem, you commented years later when the error was hidden in the history
    – Ben Voigt
    Mar 4, 2018 at 2:36
0

If you reframe the problem, you can solve this with calculus! This method was originally shown to me via Arthur Breitman https://twitter.com/ArthurB/status/1436023017725964290.

First, you take the integral of log(x) from 1 to n it is n*log(n) -n +1. This proves a tight upper bound since log is monotonic and for every point n, the integral from n to n+1 of log(n) > log(n) * 1. You can similarly craft the lower bound using log(x-1), as for every point n, 1*log(n) > the integral from x=n-1 to n of log(x). The integral of log(x) from 0 to n-1 is (n-1)*(log(n-1) -1), or n log(n-1) -n -log(n-1)+1.

These are very tight bounds!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.