1
$\begingroup$

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.

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

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.

$\endgroup$
4
  • $\begingroup$ If you could let me know why we did exp$(\lg n \lg(\lg n))$? $\endgroup$ Jun 5 '20 at 19:30
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Tony419
    Jun 5 '20 at 20:15
  • $\begingroup$ Ok thank you. Got it. $\endgroup$ Jun 6 '20 at 5:40
  • $\begingroup$ 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? $\endgroup$ Jun 6 '20 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.