What do we mean by polynomially upper bounded and lower bounded

Question

I just came across this asymptotic bound :

$(\log n)!= \Theta \left(n^{\log \log n}\right)$

Which had the following remark:

Hence, polynomially lower bounded but not upper bounded.

I found this here:

https://gateoverflow.in/12928/%24-log-and-log-log-are-polynomially-bounded-anybody-can-prove

I am confused on how can we conclude whether it's polynomial lower bounded and not upper bounded.

Could someone please help me on understanding this.

Answer 1

Now a polynomial is of the form,$n^{c}$ where $c$ is constant.

Now let $f(n)$ be a constant function. Now it being a constant function we have,

$f(n) \in O(lg (n))$

$\implies lg(f(n)) \in O(lg(lg(n))$

Now $lg(f(n))$ is yet another constant function and let it be $g(n)$

So we have from the previous implication,

$ g(n) \in O(lg(lg(n))$

$\implies n^{g(n)} \in O(n^{lg(lg(n)})$

$\implies n^{lg(lg(n))} \in \Omega(n^{g(n)})$

But $g(n)$ is after all a constant so let it be $c$ then we have from the previous implication,

$n^{lg(lg(n))} \in \Omega(n^{c})$

Now $n^{c}$ is a polynomial and hence $n^{lg(lg(n))}$ is polynomially lower- bounded.

We cannot have the other way around i.e. $n^{lg(lg(n))}$ is upper bounded by a polynomial simply because of the observation, $n^{c} \in O(n^{lg(lg(n)})$ as clearly $lg(lg(n)$ shoots up faster(no doubt) than $c$ a constant.