I know this question has already been asked a lot of times before as mentioned:
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.
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.