What is O(log(n!)) and O(n!) and Stirling Approximation
Solution 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.
Solution 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).