2
$\begingroup$

My computer science professor has us tasked with proving or disproving the statement $n! = O(2^n)$. We are then supposed to say if it's always true, always false, or non-conclusive (true in some cases but false in other cases).

So I believe that the statement $n! = O(2^n)$ is non-conclusive for the sole reason that it isn't true until $n\geq4$. I'm having a hard time proving the inductive step of my mathematical induction. Below is what I have so far, could someone help me out figure the induction step?


Problem $\boldsymbol 1$(c) Is the statement True, False, or non-conclusive? Non-conclusive meaning true in some cases but false in other cases.

Question. $C(n) =n!$ implies that $C(n) =O(2^n)$ $\longleftarrow$ Prove or disprove

Given: $2^n \leq n!$

For $n=1$, we have $2^1 \leq 1! \implies 2\leq1$ which is FALSE.
For $n=2$, we have $2^2 \leq 2! \implies 4\leq2$ which is FALSE.
For $n=3$, we have $2^3 \leq 3! \implies 8\leq6$ which is FALSE.
For $n=4$, we have $2^4 \leq 4! \implies 16\leq24$ which is TRUE.

From pluging in some values we see that $n!$ seems to grow faster than $2^n$. Let's try and prove that through mathematical induction.

Let us suppose the following property $P(n)$ defined thusly: $$2^n \leq n! \quad \text{for all integers } n \geq 4.$$

Mathematical Induction Proof:

Step $1$. Prove the Basis step, we must show $P(4)$ is true. $$P(n) =2^n \leq n! \longrightarrow 2^4 \leq 4! \implies 16 \leq 24,$$ which is true.

Step $2$. Prove the inductive step, now suppose this works for any integer $k$, $k \leq 4$ such that $$2^k \leq k! \longleftarrow \text{inductive hypothesis}$$

Now to complete mathematical induction proof, we must show that the following is true for $P(k+1)$: \begin{align} 2^{k+1} &\leq (k+1)! \\ (2^k)(2) &\leq (k+1)(k!) \end{align}

$\endgroup$
7
  • 2
    $\begingroup$ You don't seem to understand what $n!=O(2^n)$ means. What do you think it means? $\endgroup$
    – anon
    Sep 14, 2014 at 0:11
  • $\begingroup$ BigOh intuitively means that in this case n! grows at a rate equal or at most 2^n. The statement is trying to claim that n! grows at most 2^n which I know to be false since n! grows way faster than any exponential function based on the graph/chart in my computer science textbook. $\endgroup$ Sep 14, 2014 at 0:14
  • $\begingroup$ Your intuition is fairly good. But proving $2^n<n!$ is not enough to disprove $n!=O(2^n)$. Do you understand why it's not enough? You need to understand what $n!=O(2^n)$ means! $\endgroup$
    – anon
    Sep 14, 2014 at 0:19
  • $\begingroup$ Nope, I don't understand why it's not enough. Honestly, I think it's enough, but have no means to back my statement up. Please teach me, whacka. :) This is quite frankly my first exploration in proof, this is an introduction to algorithm's class I'm taking. Maybe I don't really understand the meaning thoroughly then, there are holes in my understanding I won't lie. $\endgroup$ Sep 14, 2014 at 0:23
  • $\begingroup$ Go back and reread the definition of $n!=O(2^n)$. $\endgroup$
    – anon
    Sep 14, 2014 at 0:26

3 Answers 3

0
$\begingroup$

Hint: Stirling's approximation tells you $\log n! = n \log n - n + O(\log n)$ or that $n! \sim \sqrt{n} \left( n / e \right)^n$ where $\sim$ neglects a constant.

Alternatively, assume $n! \in O(2^n)$. Then there would exists a constant $0 < k < \infty$ such that $n! \leq k 2^n$. Show something goes wrong with this for n larger than some $N$ (which is in terms of $k$).

$\endgroup$
3
  • $\begingroup$ Stirling's is probably a bad idea pedagogically. One can easily show that $2^n/n!\to0$ though... $\endgroup$
    – anon
    Sep 14, 2014 at 0:22
  • $\begingroup$ whacka, I know of L'Hopital's rule and that it can be used to prove that n! factorial grows faster than 2^n, but I'm not allowed to use that. Batman, I don't know about Stirling's approximation. $\endgroup$ Sep 14, 2014 at 0:25
  • $\begingroup$ @Twilight I am thinking much, much more basic than calculus tools. $\endgroup$
    – anon
    Sep 14, 2014 at 0:26
0
$\begingroup$

Outline: Divide $1\cdot 2\cdot 3\cdot 4\cdot 5\cdots n$ by $2\cdot 2\cdot 2\cdot 2\cdots 2$. Since $\frac{4}{2}\ge 2$ and $\frac{5}{2}\ge 2$ and so on, for $n\ge 3$ the ratio is $\ge \frac{3}{2}2^{n-3}$.

If one feels like it, one can do this more formally by induction. The inequality holds at $n=3$, and the induction step is easy.

$\endgroup$
2
  • $\begingroup$ How is this relevant to my question? It looks nothing like the factorial and neither is the ratio. I might not be up to par yet with all this proof business, it seems. :/ So this can be done by induction, huh? :D $\endgroup$ Sep 14, 2014 at 1:41
  • $\begingroup$ The relevance is that it is a complete solution to the problem, and shows that $n!$ is not big $O(2^n)$, In fact it shows that $2^n/n!$ approaches $0$ as $n\to\infty$, that $n!$ grows much faster than $2^n$. The product $1\cdot 2\cdots n$ is $n!$. You had the essence of the argument, but did not quite see that it did the job. $\endgroup$ Sep 14, 2014 at 5:47
0
$\begingroup$

The statement $n! = O(2^n)$ means that there is a positive $c$ and a positive integer $N$ such that $n! \le c 2^n$ for $n \ge N$, or $r(n) =\frac{n!}{2^n} \le c $ for $n \ge N$.

Choosing $n \ge \max(N, 4)$, $r(n+1) =\frac{(n+1)!}{2^{n+1}} =\frac{n+1}{2}\frac{n!}{2^n} >2r(n) $. By induction, $r(n+k) > 2^k r(n) $ or $r(n) <r(n+k)/2^k < c/2^k $.

Therefore $r(n)$ can be made arbitrarily small, which is a contradiction.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .