60

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.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Jiew Meng
  • 84,767
  • 185
  • 495
  • 805

2 Answers2

109

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.

Austin
  • 1,087
  • 3
  • 14
  • 27
Paul
  • 139,544
  • 27
  • 275
  • 264
  • 13
    Wow. The power of the `log`. – sarnold Nov 14 '11 at 07:00
  • 1
    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))`? – Jiew Meng Nov 14 '11 at 08:50
  • log(ab)=log(a)+log(b) would be the point when it comes to unwinding the n! into n separate factors, I believe. – JB King Jul 02 '13 at 18:32
  • 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. – kazuoua May 21 '14 at 00:19
  • 1
    @kazuoua 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))`. – Paul Nov 21 '14 at 15:11
  • 1
    @kazuoua 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. – Paul Nov 21 '14 at 15:24
  • 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. –  Apr 15 '16 at 02:45
  • 3
    @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)`. – Paul Apr 15 '16 at 02:57
  • 1
    @NickAceves It is also easy to prove by contradiction that `O(n^n)` is not in `O(n!)` using the definition of big-Oh. – Paul Apr 15 '16 at 03:05
  • Beautiful and concise proof – Bruno Masquio Aug 16 '23 at 18:21
19

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).

Ted Hopp
  • 232,168
  • 48
  • 399
  • 521