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
SUMMARY

The discussion focuses on proving that the expression (log log n) × (log log log n) is Ω(log n). The user is attempting to demonstrate that the function f(n) = ⌈(log log n)⌉! is polynomially bounded, specifically showing that log[f(n)] = Ω(log n). They have successfully established that log[f(n)] = O(log n) but are seeking assistance in proving the lower bound. The conversation highlights the need for specific constants c1 and k1 to validate the inequality.

PREREQUISITES
  • Understanding of Big O and Big Omega notation
  • Familiarity with logarithmic functions and their properties
  • Knowledge of factorial growth rates
  • Basic principles of asymptotic analysis
NEXT STEPS
  • Study the properties of logarithmic functions in asymptotic analysis
  • Research techniques for proving lower bounds in algorithm analysis
  • Explore the relationship between factorial growth and logarithmic bounds
  • Learn about the application of the Master Theorem in complexity proofs
USEFUL FOR

This discussion is beneficial for computer scientists, mathematicians, and algorithm analysts who are interested in asymptotic notation and the analysis of logarithmic functions in computational complexity.

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
4K
  • · Replies 10 ·
Replies
10
Views
5K
  • · Replies 2 ·
Replies
2
Views
7K
  • · Replies 10 ·
Replies
10
Views
6K