# What do we mean by polynomially upper bounded and lower bounded

I just came across this asymptotic bound :

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

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.

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.

• But if we consider f(n) a constant function doesn't it mean f(n) would produce a constant value regardless of the input n? Please correct me if I am wrong Jun 7 '20 at 7:54
• yes you are correct Jun 7 '20 at 7:55
• But if we take $f(\log n)$ won't this change? To get to $O(\log n)$. The values would differ for every $n$. Jun 7 '20 at 7:57
• $f(n)$ is independent of $n$, it won't change even if you put in a very large function such as $n^{n}$ Jun 7 '20 at 8:00
• In which portion are you facing the confusion. Do not forget the basic definition of the big oh , big omega in CLRS and then try to imagine the curves of the functions, you can use desmos for the same and change the constant,(hidden in the big oh, big omega and big theta, rather all the asymptotic notations and then convince your self whether at all there exists a $c$ such that for all $n \geqslant n_0$ one curve overpowers the other) Jun 7 '20 at 8:06