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

  • Thread starter Thread starter 22990atinesh
  • Start date Start date
  • Tags Tags
    Asymptotics Log
Click For Summary
The discussion focuses on proving that (log log n) × (log log log n) = Ω(log n). The user is attempting to show that f(n) = ⌈(log log n)⌉! is polynomially bounded, specifically that log[f(n)] = Ω(log n). They have successfully demonstrated that log[f(n)] = O(log n) but are struggling with the Ω(log n) proof. There is a suggestion that finding appropriate constants c1 and k1 could simplify proving the left inequality. The conversation emphasizes the need for a clearer approach to establish the lower bound.
22990atinesh
Messages
143
Reaction score
1
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.
 
Physics news on Phys.org
For the original problem, isn't it trivial to find c1, k1 to make the left inequality right?
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 12 ·
Replies
12
Views
2K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 7 ·
Replies
7
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 6 ·
Replies
6
Views
3K
  • · Replies 10 ·
Replies
10
Views
2K
  • · Replies 10 ·
Replies
10
Views
4K
  • · Replies 2 ·
Replies
2
Views
6K
  • · Replies 10 ·
Replies
10
Views
6K