Prove that n! is not in O(n^p) for any constant natural number p

Tag: math , proof , proofs Author: peny3 Date: 2010-10-21

How can I prove that n! is not in O(n^p) for any constant natural number p? And is (n k)(n choose k) in O(n^p), for all k?

@Mitch: If you made that an answer, I'd upvote it.

Other Answer1

Stirling's approximation says that

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

But

log (n^p) = p log n = O(log n)

for constant p. Clearly n! grows faster than n^p and hence it is not O(n^p).

comments:

You could also note without using stirlings approximation that log(n!)=log(n)+log(n-1)+...+log(2)+log(1). log(1)=0, so every other term has to be at least log(2) or larger. That gives log(n!) > n*log(2), which of course means it's O(n). As you noted it's actually O(n*log n), but O(log n) also grows way faster than O(log n).
+1. I was attempting not to do the homework for them ;). but I probably should have hinted at Stirling's factorial approximation.

Other Answer2

You can prove that n! is not in O(n^p) for any constant natural number p, by showing that you can always choose n (for a fixed constant p), so that n! > n^p.

(to get an idea, pick a few low values of p and plot n! against n^p)

The reasoning for the second part follows the same lines. Bound (n choose k) and then use first part.

Hint: as Casablanca noted, you can use Stirling's approximation

comments:

To be precise, for all n > n0, where n0 is some positive integer. You can't choose a single value n. Counterexample: p=10, n=2. 2^10 > 2!.
I'm sorry, I should revise that comment. To disprove n! = O(n^p): given p, then for any n0 > 0, there exists a (single) value n > n0 such that n! > n^p.

Other Answer3

Edit (3/2011) - easier method using only simple calculus

One way to show O(n!) does not equal O(n^p) is to compare the log of n! with the log of n^p.

ln(n!) = sum(ln(i)) {i: 1 to n}

ln(n^p) = p*ln(n)

That doesn't seem to help since we don't know what the sum of the logs would be. The trick is to calculate a lower bound by using the integral of ln(i)di from 1 to n

This can be seen in the image below that the ln(x) in black is less than the sum step function in blue.

enter image description here

Given that the indefinite integral of ln(i)di is i*ln(i) - i + C, we can integrate from 1 to n to get:

n*ln(n) - n + 1 as the lower bound.

And because no p can be chosen that is larger than all possible n:

O(p*ln(n)) < O(n*ln(n)), O(n^p) < O(n!)

note: integrating ln(n) to get an approximation to ln(n!) is the basis for Stirling's approximation. This is a rougher approximation and if you continue it by taking the anti-log: n! >= e*(n/e)^n, whereas Stirling's has sqrt(2*pi*n) instead of e.

Integrating from 1 to n+1 would give you an upper bound (the sum step function would fit inside the graph of ln(n))