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