0

Is $$\log \log n \times \log \log \log n = \Omega(\log n) $$ How can we prove it.

Actually I'm trying to prove that $f(n) = \lceil(\log \log n)\rceil !$ is polynomially bounded. It means

$$c_1 n^{k_1} \leq f(n) \leq c_2 n^{k_2} \quad \forall n > n_0$$ $$m_1 \log n \leq \log [f(n)] \leq m_2 \log n$$ $$\log [f(n)]=\theta(\log n) \text{ i.e. } \log [f(n)]=\Omega(\log n) \text{ and }\log [f(n)]=O(\log n) $$

I've proved that $\log [f(n)] = O(\log n)$, But I'm having trouble proving $\,\log \left[f(n)\right] = \Omega\left(\log n\right)$. Can anybody tell me how can we do it.

Atinesh
  • 1,239

1 Answers1

0

You will not be able to prove this. $f(n)$ grows asymptotically slower than any polynomial, i.e. $f(n) = n^{o(1)}$. Indeed, for any $c > 0$ $$ n^c = 2^{c\log n} $$ while $$f(n) = 2^{\Theta(\log\log n\cdot \log\log\log n)}$$ as you showed. But $$ \frac{\log\log n\cdot \log\log\log n}{\log n} < \frac{(\log \log n)^2}{\log n} \xrightarrow[n\to\infty]{} 0 $$

Edit: this does not contradict the fact that $f(n)$ is polynomially bounded. It is: it is asymptotically bounded (above) by any polynomial.

Clement C.
  • 67,323
  • Then How can we prove that ⌈(log logn)⌉! is polynomially bounded. – Atinesh Aug 15 '15 at 12:40
  • You did already: showed a polynomial upper bound upper bound (you wrote you did prove $\log f(n) = O(\log n))$ already). The lower bound, however, does not hold (but you do not need it). – Clement C. Aug 15 '15 at 12:41
  • I'm really Sorry, there has been a typing mistake I didn't recognize it. Please see the updated question. – Atinesh Aug 15 '15 at 14:52
  • The same proof applies -- if $\log f(n) = o(\log n)$ (and it is), then you have $\log f(n) = O(\log n)$ but cannot have $\log f(n) = \Omega(\log n)$. – Clement C. Aug 15 '15 at 14:57
  • I think I'm having a little bit confusion. Does Polynomially Bounded means Upper bounded by polynomial or lower and upper bounded by polynomial. – Atinesh Aug 15 '15 at 15:02
  • I would bet on the former here, since the latter is not true... – Clement C. Aug 15 '15 at 15:02
  • C One more thing. Could you please see the image below and tell whether I'm using the notation properly or not

    http://s10.postimg.org/4ccxk8xqh/Screenshot_from_2015_08_15_21_21_41.png

     – Atinesh Aug 15 '15 at 15:53
  • \theta should be \Theta, you are missing parentheses at the beginning around the (loglog n)! (It's ambiguous), and the square should be inside the o(), not outside (I.e., add parentheses there too). Otherwise, at first glance it looks fine. – Clement C. Aug 15 '15 at 15:59
  • ok Thanks @Clement C – Atinesh Aug 15 '15 at 16:54