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

In summary, the conversation is about proving that ##\log \log n \times \log \log \log n = \Omega(\log n)## and the difficulty in proving that ##\log [f(n)] = \Omega(\log n)## for the function ##f(n) = \lceil(\log \log n)\rceil !##, which is required to show that it is polynomially bounded. The speaker has already proved that ##\log [f(n)] = O(\log n)## but is struggling to prove the other inequality.
  • #1
22990atinesh
143
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
  • #2
For the original problem, isn't it trivial to find c1, k1 to make the left inequality right?
 

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

1. What does the notation Ω(logn) mean?

The notation Ω(logn) represents the lower bound of a function, meaning that the function grows at least as fast as logn. It is commonly used in asymptotic analysis to compare the growth rates of different functions.

2. Can you provide an example of a function that satisfies the condition (log logn)×(log log log n) = Ω(logn)?

One example of a function that satisfies this condition is f(n) = logn. As n increases, the value of f(n) also increases, and it satisfies the condition that (log logn)×(log log log n) is at least a constant multiple of logn.

3. How can you prove that (log logn)×(log log log n) = Ω(logn)?

To prove that (log logn)×(log log log n) = Ω(logn), we can use the limit definition of big-Ω notation. This means showing that for any positive constant c, there exists a value N such that for all n > N, (log logn)×(log log log n) is greater than or equal to c×logn. This can be proved using mathematical induction or by using the properties of logarithmic functions.

4. Is it possible for (log logn)×(log log log n) to be equal to Ω(logn)?

No, it is not possible for (log logn)×(log log log n) to be equal to Ω(logn). This is because the notation Ω(logn) represents the lower bound of a function, while (log logn)×(log log log n) represents the upper bound. Therefore, they cannot be equal.

5. Can this equation be applied to any type of function?

Yes, this equation can be applied to a wide range of functions. As long as the function satisfies the condition (log logn)×(log log log n) = Ω(logn), this equation can be used to analyze its growth rate and complexity. It is commonly used in the field of computer science to analyze the time complexity of algorithms.

Similar threads

Comp Sci Big O/Little O, Big Ω, little ω
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
I Relation with Hessian and Log-likelihood
    • Set Theory, Logic, Probability, Statistics
Replies
12
Views
1K
I Analytic continuation of Dilogarithm
    • Topology and Analysis
Replies
7
Views
1K
Optimization: How to find the dual problem?
    • Calculus and Beyond Homework Help
Replies
6
Views
1K
MHB Upper Bound for Recurrence Relation: $T(n) \leq c n^2 \log^2 n$
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
MHB A decision tree has an expected depth of at least log n
    • Programming and Computer Science
Replies
1
Views
1K
Number of unique prime factors of n is O(log n/(log log n))?
    • Calculus and Beyond Homework Help
Replies
10
Views
1K
Comp Sci Proofing Big-O Notation: O(max(f(n), g(n)))
    • Engineering and Comp Sci Homework Help
Replies
4
Views
2K
I Understanding Theorem 13 from Calculus 7th ed, R. Adams, C. Essex, 4.10
    • Calculus
Replies
10
Views
2K
I Express the limit as a definite integral
    • Calculus
Replies
16
Views
3K

Hot Threads

Recent Insights

Back
Top