Es $(\log(n))!$ una función polinomialmente acotada?

Question

¿Es cierta la siguiente afirmación? ¿Cómo lo demostrarías?
es decir, ¿está acotado polinomialmente?

$$ \lceil \lg(n) \rceil ! \in O(n^k) $$

¿Qué tal si $$ \lceil \lg \lg(n) \rceil ! \in O(n^k) $$

¡Muchas gracias!

Answer 1

Pista nº 1: Mira La aproximación de Stirling .

Pista #2: $\ln n^{\ln n} = \left(e^{\ln \ln n}\right)^{\ln n} = e^{\left(\ln n\cdot \ln\ln n\right)} = ?$ (Tenga en cuenta que utilizo $\ln$ en lugar de $\lg$ (pero las bases de los troncos no hacen ninguna diferencia real aquí - ¡convéncete de eso, sin embargo!)

Answer 2

Un comienzo: Al considerar $(1\cdot 2\cdot 3\cdots \cdot w)(w\cdot (w-1) \cdot (w-2)\cdots \cdot 1)$ podemos demostrar que $(w!)^2\ge w^{w}$ y por lo tanto $w!\ge w^{w/2}$ .

Dejemos que $w=\log n$ .

Para el segundo problema, el límite superior $w!\le w^w$ (para $w\gt 0$ ) es suficiente.