Show 2^n is O(n!)

To prove that 2ⁿ is O(n!), you need to show that 2ⁿ ≤ M·n!, for some constant M and all values of n ≥ C, where C is also some constant.

So let's choose M = 2 and C = 1.

For n = C, we see that 2ⁿ = 2 and M·n! = 2, so indeed in that base case the 2ⁿ ≤ M·n! is true.

Assuming it holds true for some n (≥ C), does it also hold for n+1? Yes, because if 2ⁿ ≤ M·n! then also 2ⁿ⁺¹ ≤ M·(n+1)!

The left side gets multiplied with 2, while the right side gets multiplied with at least 2.

So this proves by induction that 2ⁿ ≤ M·n! for all n ≥ C, for the chosen values for M and C. By consequence 2ⁿ is O(n!).