# How to prove that $\left(\log \log n\right) \times \left(\log \log \log n\right) = Ω\left(\log n\right)$

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.

• The claim is the title is wrong: $\log\log n \cdot \log\log\log n = o(\log n)$. – Clement C. Aug 15 '15 at 12:22
• Can you define the symbols you use? – Paolo Leonetti Aug 15 '15 at 12:22
• @ClementC. f(n) = o(g(n)) then f(n)= O(g(n)) also. – Atinesh Aug 15 '15 at 12:25
• – Clement C. Aug 15 '15 at 12:29
• (I also suspect you wanted $\Omega(\cdot)$ instead of $\omega(\cdot)$; the claim is still false then, however.) – 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.
• 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
• 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