Is $(\log(n))!$ a polynomially bounded function?

Question

Is the following statement true? How would you prove it?
i.e. Is it a polynomially bounded?

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

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

Thanks a lot!

Answer 1

Hint #1: Look at Stirling's approximation.

Hint #2: $\ln n^{\ln n} = \left(e^{\ln \ln n}\right)^{\ln n} = e^{\left(\ln n\cdot \ln\ln n\right)} = ?$ (Note that I use $\ln$ rather than $\lg$, but the bases of the logs don't make any real difference here - convince yourself of that, though!)

Answer 2

A start: By considering $(1\cdot 2\cdot 3\cdots \cdot w)(w\cdot (w-1) \cdot (w-2)\cdots \cdot 1)$, we can show that $(w!)^2\ge w^{w}$, and therefore $w!\ge w^{w/2}$.

Let $w=\log n$.

For the second problem, the upper bound $w!\le w^w$ (for $w\gt 0$) is enough.