Introduction

The intended question here is usually whether log(n!) grows on the order of n log n. The answer is yes: log(n!) = Θ(n log n), and you can prove it cleanly with either bounds on a sum or Stirling's approximation.

Rewrite the Expression as a Sum

The first step is to expand the factorial inside the logarithm:

log(n!) = log(1 · 2 · 3 · ... · n)
        = log 1 + log 2 + log 3 + ... + log n

So the problem becomes understanding the growth of the sum:

sum from i = 1 to n of log i

That sum is larger than logarithmic growth and smaller than quadratic growth. Intuitively, most terms near the end are about as large as log n, and there are n of them, so n log n is the natural target.

Prove the Upper Bound

For every i between 1 and n, we have log i <= log n. Therefore:

log(n!) = sum log i <= n log n

That immediately gives:

log(n!) = O(n log n)

The upper bound is straightforward because none of the terms in the sum can exceed the largest one.

Prove the Lower Bound

For the lower bound, focus only on the second half of the product. If i is between n / 2 and n, then log i >= log(n / 2). There are about n / 2 such terms, so:

log(n!) >= (n / 2) log(n / 2)

Expand that:

(n / 2) log(n / 2) = (n / 2)(log n - log 2)

The log 2 term is just a constant, so this is still proportional to n log n for sufficiently large n. That gives:

log(n!) = Ω(n log n)

Since we now have both the upper and lower bound, the result follows:

log(n!) = Θ(n log n)

A Short Proof in Python Terms

If you want to see the growth numerically, compare log(n!) with n log n for increasing n.

1import math
2
3for n in [10, 100, 1000, 10_000]:
4    left = math.lgamma(n + 1)   # log(n!)
5    right = n * math.log(n)
6    print(n, left / right)

math.lgamma(n + 1) returns log(n!) without overflowing on large factorials. The ratio does not blow up or collapse toward zero; it stabilizes around a constant scale, which is exactly what Θ notation describes.

Stirling's Approximation Gives the Same Result

Stirling's formula says:

n! ~ sqrt(2πn) (n / e)^n

Take the logarithm:

log(n!) = log(sqrt(2πn)) + log((n / e)^n)
        = (1 / 2) log(2πn) + n log n - n

The dominant term is n log n. The other pieces, namely -n and (1 / 2) log(2πn), grow more slowly in asymptotic terms. So Stirling gives the same conclusion:

log(n!) = n log n - n + O(log n)

That is a stronger statement than Θ(n log n) because it shows the main term and the lower-order corrections.

Why the Logarithm Base Does Not Matter

In asymptotic analysis, the base of the logarithm changes only by a constant factor:

log_a n = log_b n / log_b a

Since Θ ignores constant multiplicative factors, the statement remains true whether you use base 2, base e, or base 10.

Where This Result Appears

This bound shows up in sorting and combinatorics. For example, comparison sorting lower bounds are tied to log(n!) because there are n! possible orderings of the input, and a decision tree must distinguish among them.

That is one reason the expression matters in algorithm analysis: it connects counting arguments to runtime lower bounds.

Common Pitfalls

One common mistake is to think the sum of logs behaves like just log n because the terms themselves are logarithms. But there are n terms, so the total is much larger.

Another mistake is proving only the upper bound and stopping there. To claim Θ(n log n), you need both an O(n log n) bound and an Ω(n log n) bound.

People also sometimes worry about log base. In asymptotic notation, the base only affects constant factors, so it does not change the Θ class.

Finally, do not confuse log(n!) with log n! as a parsing issue in plain text. In mathematics and algorithm analysis, the intended expression is almost always log(n!).

Summary

• 'log(n!) can be rewritten as the sum of log i from 1 through n.'
• The upper bound follows from log i <= log n.
• The lower bound follows by keeping only about half the terms, each at least log(n / 2).
• Stirling's approximation gives the stronger form n log n - n + O(log n).
• Therefore log(n!) = Θ(n log n).