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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.

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(pln(n)) < O(nln(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))