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.

  • 3
    $\begingroup$ The claim is the title is wrong: $\log\log n \cdot \log\log\log n = o(\log n)$. $\endgroup$ – Clement C. Aug 15 '15 at 12:22
  • 1
    $\begingroup$ Can you define the symbols you use? $\endgroup$ – Paolo Leonetti Aug 15 '15 at 12:22
  • $\begingroup$ @ClementC. f(n) = o(g(n)) then f(n)= O(g(n)) also. $\endgroup$ – Atinesh Aug 15 '15 at 12:25
  • 1
    $\begingroup$ @Atinesh Yes. But $\omega(f(n))$ does not mean what you seem to think it means. $\endgroup$ – Clement C. Aug 15 '15 at 12:29
  • $\begingroup$ (I also suspect you wanted $\Omega(\cdot)$ instead of $\omega(\cdot)$; the claim is still false then, however.) $\endgroup$ – Clement C. Aug 15 '15 at 12:38

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.

  • $\begingroup$ Then How can we prove that ⌈(log logn)⌉! is polynomially bounded. $\endgroup$ – Atinesh Aug 15 '15 at 12:40
  • $\begingroup$ 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). $\endgroup$ – Clement C. Aug 15 '15 at 12:41
  • $\begingroup$ I'm really Sorry, there has been a typing mistake I didn't recognize it. Please see the updated question. $\endgroup$ – Atinesh Aug 15 '15 at 14:52
  • $\begingroup$ 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)$. $\endgroup$ – Clement C. Aug 15 '15 at 14:57
  • $\begingroup$ I think I'm having a little bit confusion. Does Polynomially Bounded means Upper bounded by polynomial or lower and upper bounded by polynomial. $\endgroup$ – Atinesh Aug 15 '15 at 15:02

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.