What do we mean by polynomially upper bounded and lower bounded
-
29-09-2020 - |
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.
Solution
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.