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

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 2

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