Question

Show that n! is not$\mathbf{O}\left(2^n\right)$

Short answer

n! is not$O\left(n^2\right)$ from theproof by contradiction.

Step-by-step solution

Definition of Big-O  Notation

Letfandgbe functions from the set of integers or the set of real numbers to the set of real numbers. We say that$f\left(x\right)$is$O\left(g\right(x\left)\right)$if there are constants C and k such that

$\left|f\right(x\left)\right|\le C\left|g\right(x\left)\right|$

Whenever$x>k$

 To prove n! is not O(2n)

By the proof by contradiction,

Let us assume n! is $O\left(2^n\right)$. Thenthere are constants C and k such that

$|n!|\le C\left|2^n\right|$

Whenever$n>k$

Divide by$\left|2^n\right|$on both sides,

$$\begin{gathered} \frac{|n!|}{\left|2^n\right|}\le \frac{C\left|2^n\right|}{\left|2^n\right|} \\ \frac{|n!|}{\left|2^n\right|}\le C \end{gathered}$$

Final Solution

Let$k>2$ for $n>2$, then,

$$\begin{gathered} \frac{n!}{2^n}=\frac{n}{2}\cdot \frac{n-1}{2}\cdot \frac{n-2}{2}\cdot \dots \cdot \cdot \frac{2}{2}\cdot \frac{1}{2} \\ \ge \frac{n}{2}\cdot 1\cdot 1\cdot 1\cdot \dots \dots \cdot 1\cdot \frac{1}{2} \end{gathered}$$

$\frac{n!}{2^n}\ge \frac{n}{4}$ ,

Now combing with the previous inequality we get,

$\frac{n}{4}\le \frac{n!}{2^n}\le C$

Here the function$f\left(n\right)=\frac{n}{4}$is not bounded as n is large.

Hence our assumption n! is $O\left(2^n\right)$is false.