1
$\begingroup$

I have been searching for a while now but couldn't find anything about this exact pair of functions with the little $\mathcal{o}$ notation.

Given the functions $f(n) = 2^{n}$ and $g(n) = n!$ I am supposed to prove, or disprove, the following statement: $f(n) \in \mathcal{o}(g(n))$.

I am fairly sure that it's true but now I need an idea of how to show this. We have just started out with this whole concept and this is the second exercise, the first one being a relatively easy big $\mathcal{O}$ task. But this exercise is just beyond me right now. The only definition I am allowed to use (meaning: NO LIMITS) is $\mathcal{o}(g(n)) = \{f(n)|\forall C > 0 \exists n_{0} \forall n\geq n_{0}:f(n) < C * g(n)\}$. This means other than with big $\mathcal{O}$, where it suffices to show that there's at least one pair $C$ and a $n_{0}$ so that $f(n) \leq C * g(n)$ $\forall n \geq n_{0}$, I now have to prove that for every $C > 0$, there is such a $n_{0}$ so that the condition stated in the set is true.

I first have been thinking about the functions, and I would have an answer for $\mathcal{O}$, because you can prove with induction that $2^{n} < n!, \forall n\geq 4$. Meaning my C would be 1 here. However, I have no idea how to prove it for every C and would be grateful for any guidance! (It would already help to know how to start. Probably like, let $C$ be greater 0, and then I have to show that for any Value of this $C$, there is... because... My biggest struggle is to find meaningful estimations to get a chain of inequalities.)

$\endgroup$
  • $\begingroup$ Try using Sterling’s approximation. $\endgroup$ – prime_hit May 19 '20 at 20:52
  • $\begingroup$ $2\cdot2\cdot2\cdot2\lt1\cdot2\cdot3\cdot4$ and $\underbrace{2\cdot2\cdots2}_{n-5\ 2\text{'s}}\lt5\cdot6\cdots n-1.$ So for $n\ge5$, $\underbrace{2\cdot2\cdots2}_{n \ 2\text{'s}}\lt1\cdot2\cdot3\cdot4\cdot5\cdot6\cdots(n-1)\cdot 2= n!/(n/2)$ $\endgroup$ – John L. May 20 '20 at 0:32
3
$\begingroup$

Pick $n_0 = \max\{ -\log c, 10 \}$. Then, for all $n \ge n_0 \ge 10$: $$ 2^n = \frac{4^n}{2^n} \le \frac{4^n}{2^{n_0}} \le \frac{4^n}{1/c} = c \cdot (4^{n-10} \cdot 4^{10}) < c \cdot (4^{n-10} \cdot 10!) \le cn! $$

$\endgroup$
1
$\begingroup$

One way to prove $f(n) = o(g(n))$ is to prove that:

$\begin{align*} \lim_{n \to \infty} \frac{f(n)}{g(n)} &= 0 \end{align*}$

In this case, you know that:

$\begin{align*} \lim_{n \to \infty} \frac{2^n}{n!} &= 0 \end{align*}$

since the series for $e^x$ converges for all $x$, so it converges for $x = 2$, and the terms of a convergent series have limit 0.

Or, if you take $n \ge 2$, you see that:

$\begin{align*} \frac{2^n}{n!} &= \frac{2}{1} \cdot \frac{2}{2} \cdot \frac{2}{3} \dotsm \frac{2}{n} \end{align*}$

Each successive factor after the second is smaller than 1, so the infinite product diverges to 0. That is, you can write for $n \ge 2$:

$\begin{align*} 0 &\le \frac{2^n}{n!} \le \frac{2}{1} \cdot \frac{2}{2} \cdot \left(\frac{2}{3} \right)^{n - 2} \end{align*}$

As $n \to \infty$, the right hand side tends to 0.

$\endgroup$
  • $\begingroup$ The OP wanted a proof with quantifiers, probably as exercise $\endgroup$ – HEKTO May 20 '20 at 2:59
1
$\begingroup$

$2^n$ is the product of n numbers which are all equal to 2.

n! is the product of n numbers from 1 to n.

Once n ≥ 3, if you increase n by 1, $2^n$ is doubled, while n! is multiplied by 4 or more. So basic maths shows that for n ≥ 3, $n! ≥ 6/64 \cdot 4^n$.

Given any C > 0 from the definition, you calculate how large n would have to be to make $2^n < 6/64 \cdot 4^n$.

$\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.