2
$\begingroup$

I'm not sure how go about this question: Prove the following inequality. For a correct proof, we require a value of the constant $c>0$ and an $n \in \mathbb N$, such that $\forall n>N : f(x)<c\cdot g(n)$.

$\mathcal O(2^n) < \mathcal O (n!)$.

I'm well aware how to prove $2^n < n!$ using induction, I just don't understand how one is supposed to find a constant, etc. The only thing that springs to mind here is choosing $N = 4$, since that is when $2^n < n!$ begins to hold. If someone could clarify how I can apply the definition of Big-O notation to solve this, I would be greatful.

$\endgroup$
  • $\begingroup$ You have a typo in the definition of O: you require $c$ and $N$. You give c (=1) and N (=4) in your post -- what do you think is missing? $\endgroup$ – Raphael Jan 28 at 17:25
  • $\begingroup$ In particular, do you mean O(2^n) is in O(n!)? $\endgroup$ – Ṃųỻịgǻňạcểơửṩ Jan 28 at 17:42
1
$\begingroup$

We need to inspect the factors after that, since the factors of $n!$ grows linearly while the factors of $2^n$ stays constant. We use the first four factors and the rest of them to formulate the constant factors used for the big-O proof. It is obvious that $2^4 = 16$ while $4! = 24$. However, by observing the factors, we notice $2^n$ has $16$ as a factor and $n!$ has $24$ as a factor for all $n \geq 4$ and we factor out the first four [the first $N$] to clearly highlight that the factorial grows faster.

The factors of $\frac{1}{16} 2^n$ factors out the first $2\cdot 2 \cdot 2 \cdot 2$. It is equal to $2\cdot 2\cdot 2\,\cdot \, ... \cdot \, 2$ with $(n-4)$ factors. The factors of $\frac{1}{24}n!$ factors out $1 \cdot 2 \cdot 3 \cdot 4$ and is equal to $5 \cdot 6 \cdot 7\, \cdot \,... \cdot \, n$, again with $(n-4)$ factors. When $n = 4$ then these factored-out functions are equal to unity. In fact:

  • $2\cdot 2\cdot 2\,\cdot \, ... \cdot \, 2\cdot 2 = c_f2^n$ where $c_f = \frac{1}{16}$ whereas
  • $5 \cdot 6 \cdot 7\, \cdot \,... \cdot \, (n-1) \cdot n = c_gn!$ where $c_g = \frac{1}{24}$.

The $(n-4)$ factors of $c_f2^n$ is clearly less than the $(n-4)$ factors of $c_gn!$. We arrive at $c_f2^n < c_gn!$. Move the constant factor on the LHS to obtain $2^n < \frac{c_g}{c_f}n! = \frac{24^{-1}}{16^{-1}}n! = \frac{16}{24}n! = \frac{2}{3}n!$.

By inspecting the factors of $2^n$ and $n!$ after the initial four, and knowing that for all $n > 4:\: 2^n < n!$, we factored out the first four terms of each function and inspected the rest to determine $2^n \leq \frac{2}{3}n!$.

The formal definition of big-O states that:

$$\exists c > 0\; \exists N > 0: \forall n\; (n>N) \Longrightarrow f(n) \leq cg(n)$$

In your case, $c = \frac{2}{3} = \frac{16}{24}$ and $N = 4$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

That really makes no sense. Check out e.g. Hildebrand's "Short course on Asymptotics" for details of the meanings and usage of asymptotic notations.

In a nutshell, for typical CS use: $O(f(n))$ is some function $g(n)$ that satisfies $g(n) \le c f(n)$ for some (unspecified) positive constant $c$ for all $n \ge n_0$ for some (again unspecified) constant $n_0$. The functions $f$ and $g$ are positive in our usage. It is meant to represent some rough upper bound, in the sense that an "equation" like:

$\begin{equation*} e^{1/n} = 1 + O(1/n) \end{equation*}$

means that $e^{1/n}$ is $1 + g(n)$ (here, by the series for $e^x$ it is $g(n) = \sum_{k \ge 1} \frac{1}{k! n^k}$) and $g(n) = O(1/n)$ (the sum of the terms after the first is smaller than a constant times $1/n$, as you can check), and $g(n) = O(1/n)$. The convention is that the right hand side is a rougher expression of the left hand side, "$=$" here is not equality. For example, you can check that:

$\begin{align*} 3 \sqrt{n} &= O(n^3) \\ 17 n^3 &= O(n^3) \end{align*}$

but that doesn't mean $\sqrt{n} = 17 n^3$. If you use $O(\cdot)$ on the left hand side, make sure the right hand side is rougher. And "$<$" makes no sense whatsoever, any such inequality is subsumed by the $O(\cdot)$ itself.

| cite | improve this answer | |
$\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.