# Induction proofs in Big-O notation

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).

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

• 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? – Raphael Jan 28 '20 at 17:25
• In particular, do you mean O(2^n) is in O(n!)? – Ṃųỻịgǻňạcểơửṩ Jan 28 '20 at 17:42

## 2 Answers

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

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.