5

I had a similar problem to this saying:

Is it true that $n!$ is $O(2^n)$?

I got that to be false because if we look at the dominant power of $n!$ it results in $n^n$. So because the base numbers are not the same it is false.

Is it true that $2^n$ is $O(n!)$?

So likewise with the bases, this question should result in false, however it is true. Why? Is the approach I am taking to solve these questions wrong?

mrp
  • 5,086
Hyune
  • 101
  • By the way, it may be worth pointing out that $n^n$ is not $O(n!)$ (or, in more natural terms, $n!$ is not $\Omega(n^n)$). You may want to look up Stirling approximation formula for good bounds on the growth of $n!$. – Jakub Konieczny Mar 17 '15 at 16:31
  • Clearly state the definition of big-O, then you should see why $2^n \leq 2(n!)$ implies that $2^n$ is $O(n!)$ – Steve Jessop Mar 17 '15 at 17:04
  • When we say that a function $f(x)$ is $\text{O}(g(n))$, this has nothing to do with checking the "base numbers." Your teacher may have given you a faulty definition of big O notation. If you want an intuitive explanation of big O notation, I would explain it as a method to order functions based on how "fast" they grow. – Ryan Mar 17 '15 at 17:06

7 Answers7

10

Note that big-O only denotes an upper bound. So anything that grows at the same or lesser rate of $n!$ is $O(n!)$.

MT_
  • 19,603
  • 9
  • 40
  • 81
8

$2^n = 2 \cdot 2 \cdots 2 \le 2 \cdot 2 \cdot 3 \cdots n = 2 \cdot (n!)$ for $n\ge 2$.

lhf
  • 216,483
6

If $f(n)$ is $O(g(n))$, then there is a constant $C$ such that $f(n) \leq C g(n)$ eventually.

It turns out that $2^n$ is $O(n!)$. Can you find a constant $C$ and prove the inequality? Hint: Choose $C=2$ and try to prove $2^n \leq 2 n!$.

abnry
  • 14,664
2

Another approach:

Consider: $$\sum_{n=1}^{\infty}\frac{2^n}{n!}\tag{1}$$

We have that $\limsup_{n\rightarrow \infty}\sqrt[n]{\frac{2^n}{n!}}=\limsup_{n\rightarrow \infty}\frac{2}{\sqrt[n]{n!}}=0$

Because

$$lim_{n\rightarrow \infty}\sqrt[n]{n!}=lim_{n\rightarrow \infty}(n\cdot (n-1)\cdot (n-2)\dots2\cdot 1)^{\frac{1}{n}}\geq lim_{n\rightarrow \infty} (\frac{n}{2}\cdot \frac{n}{2}\dots \frac{n}{2})^{\frac{1}{n}}\geq lim_{n\rightarrow \infty}(\frac{n}{2})^{\lfloor \frac{n}{2}\rfloor\cdot \frac{1}{n}}=\infty$$

Hence the series in (1) is convergent by the root test. So $\frac{2^n}{n!}$ is a zero-sequence from which the statement follows.

Note that you can replace $2$ by any other number.

Marm
  • 3,371
  • 1
  • 16
  • 24
1

Yes it is true.

$$2\le2$$ $$2\cdot2\le2\cdot 3$$ $$2\cdot2\cdot2\le2\cdot 3\cdot 4$$ $$2\cdot2\cdot2\cdot2\le2\cdot 3\cdot 4\cdot 5$$

$$\cdots$$ $$2\cdot2\cdot2\cdot2\cdots2\le2\cdot 3\cdot 4\cdot 5\cdots\cdot n$$

0

There's already another anwer to this effect, but perhaps this example gives some much-needed intuition:

What are the values of the following, for $n=10$?

$2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\cdot2\\ 1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7\cdot8\cdot9\cdot10$

See why?

geometrian
  • 3,036
0

The criterion "base numbers are different" is not valid. The functions $2^n$ and $3^n$ have different bases, yet $2^n$ is $O(3^n)$. On the other hand, $3^n$ is not $O(2^n)$.

If we have fixed constants $m > k > 1$, then $k^n$ as a function of $n$ is $O(m^n)$.

Notice also that $n^n$ is an exponential with a larger base than $2^n$ whenever $n > 2$, and in general the order $O(f(n))$ of a function $f(n)$ is concerned with what happens as $n$ gets large. How "large" does $n$ have to be in order to ensure that $n > 2$?

Taking the original function in question, $n!$, again we have $2^n$ is $O(n!)$ for much the same reasons. Once $n \geq 4$, the ratio $\frac{n!}{2^n}$ grows by a factor of $2$ (or more) each time $n$ increases by adding $1$.

David K
  • 98,388