¿Existe una función que crezca más rápido que la exponencial pero más lento que el factorial?

Question

En notación big-O la clase de complejidad $O(2^n)$ se denomina "exponencial". La clase de complejidad $O(n!)$ se llama "factorial".

Creo que $f(n) = O(2^n)$ y $g(n) = O(n!)$ significa que $f(n)/g(n)$ va a cero en el límite como $n$ va al infinito.

¿Se conoce alguna función entre las clases de complejidad factorial y exponencial?

En otras palabras, ¿hay alguna función conocida $j(n)$ que domina todas las funciones de $O(2^n)$ tal que..: $$ (j(n) \neq O(2^n)) \wedge (j(n) = O(n!)) \wedge (n! \neq O(j(n))) $$ o, informalmente, $j(n)$ crece asintóticamente de forma estrictamente más rápida que $2^n$ pero no tan rápido como $n!$ ?

¿O acaso se ha demostrado que no puede existir tal función?

Nota: esto puede parecer una pregunta de Ciencias de la Computación, pero en realidad estoy tratando de demostrar que cualquier serie de potencias periódica y convergente debe tener coeficientes cuyos inversos crecen asintóticamente tan rápido como $n!$ pero no más rápido. Creo que puedo demostrar que la mayoría crecen más rápido que $O(2^n)$ pero eso no demuestra que estén en $\Theta(n!)$ a menos que no haya una clase de complejidad entre $O(2^n)$ y $O(n!)$ .

Answer 1

Sugerencia Para el exponencial tienes el crecimiento $$\frac{a_{n+1}}{a_n}=\mbox{constant}$$

Para el factorial tienes el crecimiento $$\frac{b_{n+1}}{b_n}=n$$

Tome cualquier función $g(n)$ que crece hasta el infinito más lentamente que $n$ y establecer $$\frac{c_{n+1}}{c_n}=g(n)$$

Por ejemplo, $g(n)=\sqrt{n}$ da el ejemplo $\sqrt{n!}$ dado por AntonioVargas .

Otro ejemplo interesante es $g(n)=\ln(n)$ que da $$d_n =\prod_{k=2}^n \ln(k)$$

Answer 2

Dadas dos funciones positivas cualesquiera $f$ y $g$ tal que $\frac{f(x)}{g(x)}$ tiende a cero, dejemos que $j(x) = \sqrt{f(x)g(x)}$ (este es el media geométrica de $f$ y $g$ ).

Entonces $\frac{f}{ j} = \frac{j}{ g} = \sqrt{\frac{f}{g}}$ que también debe tender a cero, por lo que $j$ es una clase de complejidad intermedia.

Answer 3

Para variar, he aquí dos llamativos ejemplos de este tipo $j$ que demuestran lo estrechas que son las clases de complejidad big-theta cuando se aplican a funciones de crecimiento tan rápido:

• $j(n) = 3^n$
• $j(n) = (n-1)!$

La primera demuestra algo que puede haber malinterpretado: el crecimiento exponencial es una clase de complejidad mucho más amplia que la mera $O(2^n)$ .

Answer 4

Muchas de las respuestas dadas son en realidad "como" el factorial: si se agrupan todas las funciones de crecimiento exponencial en una sola clase, tendría sentido agrupar cosas como $n!$ y $\sqrt{n!}$ en una sola clase también. Pero todavía hay clases intermedias.

¿Qué quiero decir con esto? Funciones como $2^n$ y $3^n$ no son realmente muy similares si los comparas directamente - $3^n$ crece mucho más rápido y no está cerca de ser $O(2^n)$ . Pero lo que los hace similares es que su logaritmos tienen el mismo crecimiento - $\log(2^n)=\Theta(\log(3^n))=\Theta(n)$ .

Ahora $\log(n!)=\Theta(n\log n)$ por lo que tendría sentido poner todas las funciones con esta propiedad - como $\sqrt{n!}$ o $(n/2)!$ o $n^n$ - en una clase general "factorial" de la misma manera que definimos la clase exponencial.

Con esta forma de pensar, está claro que todavía hay algo intermedio, que crece más rápido que cualquier cosa de tipo exponencial pero más lento que cualquier cosa de tipo factorial. Sólo tienes que elegir alguna función $f(n)$ que crece más rápido que $\Theta(n)$ pero más lento que $\Theta(n\log n)$ como por ejemplo $f(n)=n\sqrt{\log n}$ o $f(n)=n\log\log n$ y luego $\exp(f(n))$ está en una clase intermedia.

La segunda opción que sugerí para $f(n)$ te da algo muy natural: $\exp(n\log\log n)=(\log n)^n$ . (Este es el mismo tipo de función que el segundo ejemplo de N.S.).

Answer 5

Para cualquier función $f$ y $g$ , $\sqrt{fg}$ tiene un crecimiento que está entre $f$ y $g$ .