Polynomial bounds?

Question

Q1: Is the function $$\lceil{\lg n}\rceil!$$ polynomial bounded?

Q2: Is the function $$\lceil{\lg\lg n}\rceil!$$ polynomially bounded?

$$\lg = \log_2$$

Polynomially bounded: $f(n)$ is polynomially bounded if for some constants $a$ and $n$, $f(n) < cn^a$, for all $n$ greater than $n_0$.

Answer 1

$\lceil{\log n}\rceil! \geq (\log n)! \approx \bigg(\frac{\log n}{e} \bigg)^{\log n} \sqrt{2 \pi \log n}$

At the same time a polynomial function is $n^a, \ a \in \mathbb{Z^+}$, hence $$ n^a = e^{\log n^a} = (e^a)^{\log n} $$ where $e^a$ is a constant. Obviously $\frac{\log n}{e} \geq e^a \ n \ \forall \geq e^{e^{a+1}}$

Hence $\lceil{\log n}\rceil!$ grows superpolynomially

EDIT: $\exists c_1 \in \mathbb{R}^{+}$ s.t. $c_1 \log \log n \geq \lceil \log \log n \rceil$. Now denote $c_1 \log \log n=v$, hence $n=e^{e^{\frac{v}{c_1}}}, \ n^{a}=e^{ae^{\frac{v}{c_1}}}$. By Stirling's formula $v! \approx (\frac{v}{e})^{v} \sqrt{2 \pi v} > v^v$. By taking logs we get $\log v^v = v \log v < \log n^a = a e^{\frac{v}{c_1}}$. Hence $\lceil \log \log n \rceil!$ is subpolynomial

Answer 2

A polynomial bound $g(n)=cn^\alpha$ has the property that $g(2n)=2^\alpha g(n)$, i.e. $\frac{g(2n)}{g(n)}$ is bounded. But with $f(x)=\lceil\lg n\rceil!$ we have $\frac{f(2n)}{f(n)}=\lceil\lg(2n)\rceil$. For large enough $n$ this will be $>2^\alpha$ and hence sooner or later $f(n)$ will outgrow $g(n)$.

Similarly, $g(n^2)=\frac1c g(n)^2$. With $f(n)=\lceil\lg\lg n\rceil!$, we have $f(n^2)=\lceil\lg(2\lg n)\rceil!=\lceil 1+\lg\lg n\rceil!=\lceil1+\lg\lg n\rceil f(n)$. Thus if $g(n)<g(n)$, then $f(n^2)<g(n^2)$ provided $\lceil 1+\lg\lg n\rceil<\frac1cg(n)$. Since the left hand side is sublinear (and $f$ is monotonic), linear $g$ should suffice for almost all $n$.

Answer 3

Since $n! \ge (n/e)^n$, we have the lower bound $\lg \lceil \lg n \rceil ! \ge (\lg n)(\lg \lg n - \lg e)$. For every fixed integer $k$, there is some large enough threshold $N$ such that this expression dominates $\lg n^k = k \lg n$ whenever $n \ge N$. So the first expression is not polynomially bounded.

For the second expression, note that $n! \le n^n$, so $\lg \lceil \lg \lg n \rceil ! \le \lg (1+\lg\lg n)! \le (1+\lg\lg n)\lg(1+\lg\lg n)$ which is bounded above by $\lg n$ for large enough $n$. Hence $n$ (a polynomial) is an upper bound, for all $n \ge N$ for some suitable threshold $N$.