# Thread: show that n! is not O(2^n)?

1. ## show that n! is not O(2^n)?

solution:
please check if i do it write or wrong
n!=n*(n-1)*(n-2)...*3*2*1
let n=4 so we have
n!=n*(n-1)*(n-2)*(n-3)
= (n^2 - n)(n-2)(n-3)
=(n^3 -2n^2 - n^2 + 2n)(n-3)
=(n^3 -3n^2+2n)(n-3)
=n^4 - 3n - 3n^3 -3n^2 +2n^2 -6n
n!=n^4 -3n^3 - n^2 - 9n
so its big O is
O(n!)=O(n^4 -3n^3 - n^2 - 9n)
=O(n^4)
putting n=4 , we have
O(n!)=O(n^n)

which proves that n! is not O(2^n)

3. ## Re: show that n! is not O(2^n)?

Hi Annie,
I'm afraid I must say your attempt is just not right. See the attachment for a proof.