What is O(log(n!)), O(n!), and Stirling's approximation?

Question

What is O(log(n!)) and O(n!)? I believe it is O(n log(n)) and O(n^n)? Why?

I think it has to do with Stirling's approximation, but I don't get the explanation very well.

Am I wrong about O(log(n!) = O(n log(n))? How can the math be explained in simpler terms? In reality I just want an idea of how this works.

Truculent

n! is exactly what it is. Strange notation though... – Bruce

@Bruce "is exactly what it is". Aahhh.. that's too funny. – Talbert

Answer 1

O(n!) isn't equivalent to O(n^n). It is asymptotically less than O(n^n).

O(log(n!)) is equal to O(n log(n)). Here is one way to prove that:

Note that by using the log rule log(mn) = log(m) + log(n) we can see that:

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

Proof that O(log(n!)) ⊆ O(n log(n)):

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

Which is less than:

log(n) + log(n) + log(n) + log(n) + ... + log(n) = n*log(n)

So O(log(n!)) is a subset of O(n log(n))

Proof that O(n log(n)) ⊆ O(log(n!)):

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

Which is greater than (the left half of that expression with all (n-x) replaced by n/2:

log(n/2) + log(n/2) + ... + log(n/2) = floor(n/2)*log(floor(n/2)) ∈ O(n log(n))

So O(n log(n)) is a subset of O(log(n!)).

Since O(n log(n)) ⊆ O(log(n!)) ⊆ O(n log(n)), they are equivalent big-Oh classes.

Vaporizer

Thanks, I don't really get the last part log(n/2) + log(n/2) + ... + log(n/2) = floor(n/2)*log(floor(n/2))``. How does floor(n/2)*log(floor(n/2)) relate to O(log(n!)) or O(n log(n))? – Truculent

log(ab)=log(a)+log(b) would be the point when it comes to unwinding the n! into n separate factors, I believe. – Susette

If O(log(n!)) = O(nlog(n)) then O(n!) = O(n^n). When you apply log to both sides of the equation you get O(log(n!)) and O(log(n^n)) = O(nlog(n)) which is the same thing you just proved. – Horror

@Horror You can't just apply log to both sides of the equation like that. If you could, then you could also argue that O(n²) = O(n), since O(log(n²)) = O(2log(n)) = O(log(n)). – Vaporizer

@Horror The reason you can't apply log to both sides of the equivalence, is because each side is a set and sets are not in the domain of the log function. – Vaporizer

I just came across this trying to remember why O(n!) = O(n^n). They are, by the way, equivalent. You can prove this by taking the limit of n!/n^n = 0 as n goes to infinity. It is 0. The sum of of n!/n^n as n goes to infinity converges to 1.87985. Thus, they are the same complexity class. – Overprize

@NickAceves They are not equal classes. O(n!) is a strict subset of O(n^n). That "proof" makes no sense. The limit of n/n^n as n goes to infinity is also 0; same with the limit of 1/n^n. Your reasoning would prove that O(1) = O(n^n). – Vaporizer

@NickAceves It is also easy to prove by contradiction that O(n^n) is not in O(n!) using the definition of big-Oh. – Vaporizer

Answer 2

By Stirling's approximation,

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

For large n, the right side is dominated by the term n log(n). That implies that O(log(n!)) = O(n log(n)).

More formally, one definition of "Big O" is that f(x) = O(g(x)) if and only if

lim sup|f(x)/g(x)| < ∞ as x → ∞

Using Stirling's approximation, it's easy to show that log(n!) ∈ O(n log(n)) using this definition.

A similar argument applies to n!. By taking the exponential of both sides of Stirling's approximation, we find that, for large n, n! behaves asymptotically like n^(n+1) / exp(n). Since n / exp(n) → 0 as n → ∞, we can conclude that n! ∈ O(n^n) but O(n!) is not equivalent to O(n^n). There are functions in O(n^n) that are not in O(n!) (such as n^n itself).

Assisi