0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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 $\endgroup$ Jun 7 '20 at 7:54
  • $\begingroup$ yes you are correct $\endgroup$ Jun 7 '20 at 7:55
  • $\begingroup$ But if we take $f(\log n)$ won't this change? To get to $O(\log n)$. The values would differ for every $n$. $\endgroup$ Jun 7 '20 at 7:57
  • $\begingroup$ $f(n)$ is independent of $n$, it won't change even if you put in a very large function such as $n^{n}$ $\endgroup$ Jun 7 '20 at 8:00
  • $\begingroup$ 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) $\endgroup$ Jun 7 '20 at 8:06

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.