0
$\begingroup$

Prove or disprove that $\forall n \in N$ $, \, n! \in \mathcal{O}(2^n)$

My attempt:

$f(n) = n!$
$g(n) = 2^n$

First I checked if I needed to prove or disprove this statement, and to do so I computed the $\lim_{n \to \infty}{\frac{f(n)}{g(n)}}$ = $\lim_{n \to \infty}{\frac{n!}{2^n}}$ which equals $\infty$ so this statement is false.

So to disprove it, I supposed that the statement was true. Then by the definition of big-oh, there would be a $C>0$ and $n_0 > 0$ such that $n! \leq C * 2^n $ for all $n \geq n_0$. So,

$$n! \leq C * 2^n $$ $$\frac{n!}{2^n} \leq C $$ $$2^{-n}n! \leq C $$

So we have constant $C \gt 0$ and $n_0 \geq 0$ such that $2^{-n}n! \leq C $.

But I don't think this can be possible since when looking at the values as n gets larger it increases:

$$\begin{array}{c|c|c|} & \text{1} & \text{2} & \text{3} & \text{4} & \text{5} \\ \hline \text{$2^{-n}n!$} & 0.5 & 0.5 & 0.75 & 1.5 & 3.75 \\ \hline \end{array}$$

Is this the correct way to approach this question and is my solution correct? Thank you to those who help.

$\endgroup$
  • $\begingroup$ Another way to solve this would be via an inductive proof. $\endgroup$ – Q the Platypus Feb 9 '16 at 4:29
  • $\begingroup$ Listing the first few values of $2^{-n}n! $ does not constitute a proof. $\endgroup$ – anomaly Feb 9 '16 at 4:34
  • $\begingroup$ You don't need the universal quantifier there; big-O notation already contains the appropriate quantifier. $\endgroup$ – Qiaochu Yuan Feb 9 '16 at 4:53
1
$\begingroup$

Close to done - you still need to formalise the contradiction you're looking for. You've reduced it to showing that $a_n=\frac{n!}{2^n}$ isn't bounded, and indeed, it is not.

Noting that $a_n=\frac{n}{2}a_{n-1}$, we see that for $n\ge3$, $a_n\ge\frac{3}{2}a_{n-1}$, which gives that $a_n\ge \left(\frac{3}{2}\right)^{n-3}a_3$ by induction.

Hence, $a_n$ grows exponentially and thus is certainly not bounded, and your claim is proven.

$\endgroup$
0
$\begingroup$

What you have written down is not the claim you are trying to prove. It is the function $ n\mapsto n! $ itself that is not in $\mathcal{O}(n\mapsto 2^n) $, not each element of that function. (EDIT: As Qiaochu Yuan said in his comment)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.