Show that 2^n is O(n!)

This is an interview question from MS.

Answer:

n! = 2*3*...*n >= 2*2*...*2 = 2^(n-1)

Since 2^n <= 2*n! for all n, we have that 2^n = O(n!).