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?
Prove that n! is not in O(n^p) for any constant natural number p



Other Answer1
Stirling's approximation says that
But
for constant 

comments:

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 (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:

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. 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 antilog: 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)) 
Relate
 Prove or disprove n^2  n + 2 ? O(n)
 To prove lg n! = theta(n lg n) [closed]

How to prove forall n:nat, ~n
 Using Z3Py online to prove that n^5 <= 5 ^n for n >= 5
 Given ((p ? q) ? r), use the Fitch system to prove ((p ? q) ? (p ? r))
 prove n = BigO(1) using induction
 Solve recurrence of form p[n,m]==p[n,m2]+p[n1,m1]+p[n2,m]
 Where to find WinAPI constant values for P/Invoke?
 Prove max(O(f(n)), O(g(n)))=O(max(f(n), g(n))
 ^[\p{L}\p{N}]{1,50}$ >>> plus one rule
 Prove f(n) is always O(f(n1)) [closed]
 How do i prove (n^2  n)/2 is O(n^2)? [closed]
 how many n digit numbers are there with product p
 background xargs/wget not adhering to P and n limits
 Using a 'for' loop in batch file programming to display the first N natural numbers