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

Question

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.

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

score 3 · Accepted Answer · answered Jun 05 '20 at 19:20

3

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.

answered Jun 05 '20 at 19:20

Tony419

772

If you could let me know why we did exp$(\lg n \lg(\lg n))$? – Sachin Bahukhandi Jun 05 '20 at 19:30
1

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)$. – Tony419 Jun 05 '20 at 20:15
Ok thank you. Got it. – Sachin Bahukhandi Jun 06 '20 at 05:40
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? – Sachin Bahukhandi Jun 06 '20 at 18:15

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

1 Answers1