# Proving $\lceil{\lg n}\rceil!$ is not polynomially bounded.

I know this question has already been asked a lot of times before as mentioned:

Polynomial bounds?

Is $\lceil{\lg n}\rceil!$ polynomially bounded?

But what I could not understand it is how to prove that it is not polynomial bounded. According to the Book Introduction to Algorithms:

We say that a function $$f(n)$$ is polynomially bounded if $$f(n)= O(n^k)$$ for some constant $$k$$.

Thereby using Stirling approximation I could easily get: $$(\lg n)^{\lg n}$$ omitting the constant values: $$e^{-\lg n}\sqrt{2\pi\lg n}$$

So for $$\lceil\lg n\rceil!$$ to be proved as a polynomial it should follow:

There would exist constants $$c$$, $$k$$ and $$n_0$$ such that $$0\le\lceil\lg n\rceil!\le c {n^k}$$ for all $$n\ge n_0$$

But do not know how to prove it further. Could someone please help me out in figuring this out. Thank you.

• is $\lg n = \frac{\ln n}{\ln 10}$?
– Alex
Jun 5 '20 at 20:34

In the answers that you cited the problem is essentially reduced to studying the expression $$\log(n)^{\log(n)} = \exp ( \log(n) \log(\log(n))) = n^{\log(\log(n))}.$$ Since $$\lim_{n\rightarrow\infty}\log(\log(n))=\infty$$ there cannot exist a constant $$C>0$$ and $$k$$ such that $$n^{\log(\log(n))}\le Cn^k.$$ In other words, $$n^{\log(\log(n))}$$ is not polynomially bounded.
• If you could let me know why we did exp$(\lg n \lg(\lg n))$? Jun 5 '20 at 19:30
• We wanted to represent $\log(n)^{\log(n)}$ as a power of $n$, in order to compare it with $n^k$ later, so we used the identity $\log (a^b)=\exp(b\log a)$. Jun 5 '20 at 20:15
• Also could you please explain me this statement if you do not mind: $\Theta \left(n^{\log \log n}\right)$ is polynomially lower bounded but not upper bounded. I am confused on how the author conclude that it falls in Omega? Jun 6 '20 at 18:15