# How to prove that (log logn)×(log log log n) = Ω(logn)

Tags:
1. Aug 15, 2015

### 22990atinesh

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.

2. Aug 15, 2015

### Staff: Mentor

For the original problem, isn't it trivial to find c1, k1 to make the left inequality right?