Is $(\log(n))!$ a polynomially bounded function? 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!

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!)
