¿Es cierto que $2^n$ es $O(n!)$ ?

Question

Tuve un problema similar a este dicho:

¿Es cierto que $n!$ es $O(2^n)$ ?

Tengo que es falso porque si nos fijamos en el poder dominante de $n!$ resulta en $n^n$ . Por lo tanto, como los números de base no son los mismos, es falso.

¿Es cierto que $2^n$ es $O(n!)$ ?

Así que al igual que con las bases, esta pregunta debería resultar falsa, sin embargo es verdadera. ¿Por qué? ¿El enfoque que estoy adoptando para resolver estas preguntas es erróneo?

Answer 1

Nótese que big-O sólo denota un límite superior. Así que cualquier cosa que crezca a la misma o menor tasa de $n!$ es $O(n!)$ .

Answer 2

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

Answer 3

Si $f(n)$ es $O(g(n))$ entonces hay una constante $C$ tal que $f(n) \leq C g(n)$ finalmente.

Resulta que $2^n$ es $O(n!)$ . ¿Puede encontrar una constante $C$ y demostrar la desigualdad? Pista: Elige $C=2$ y tratar de demostrar $2^n \leq 2 n!$ .

Answer 4

Otro enfoque:

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

Tenemos que $\limsup_{n\rightarrow \infty}\sqrt[n]{\frac{2^n}{n!}}=\limsup_{n\rightarrow \infty}\frac{2}{\sqrt[n]{n!}}=0$

Porque

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

Por lo tanto, la serie en (1) es convergente por la prueba de raíz. Así que $\frac{2^n}{n!}$ es una secuencia cero de la que se desprende la afirmación.

Tenga en cuenta que puede sustituir $2$ por cualquier otro número.

Answer 5

Ya hay otra respuesta a este efecto, pero tal vez este ejemplo dé una intuición muy necesaria:

¿Cuáles son los valores de lo siguiente, para $n=10$ ?

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

¿Ves por qué?