Menu
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 Approximation, but I don't get the explanation very well.
Could someone correct me if I'm wrong (about O(log(n!) = O(n log(n)))? And if possible the math in simpler terms? I don't think I will need to prove that in reality I just want an idea of how this works.
979
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.
Logarithmic time complexity log(n): Represented in Big O notation as O(log n), when an algorithm has O(log n) running time, it means that as the input size grows, the number of operations grows very slowly.
Stirling's approximation is named after the Scottish mathematician James Stirling (1692-1770). In confronting statistical problems we often encounter factorials of very large numbers. The factorial N! is a product N(N−1)(N−2)...(
O(logn) means that the algorithm's maximum running time is proportional to the logarithm of the input size. O(n) means that the algorithm's maximum running time is proportional to the input size. basically, O(something) is an upper bound on the algorithm's number of instructions (atomic ones).
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.
87
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
