How is O(log(log(n))) also O(logn)? I have seen this result somewhere with this but I still didn't quite understand how this is true. This would also help me compute Big Omega of the same function.

Chaim Ferguson

Chaim Ferguson

Answered question

2022-10-13

How is O ( log ( log ( n ) ) ) also O ( log n )?
I have seen this result somewhere with this but I still didn't quite understand how this is true. This would also help me compute Big Omega of the same function.

Answer & Explanation

getrdone07tl

getrdone07tl

Beginner2022-10-14Added 23 answers

Suppose f ( n ) = O ( log log n ), and we want to prove that f ( n ) = O ( log n )
Assume f ( n ) is a positive function. By the definition of the big O notation, f ( n ) = O ( log log n ) implies that there exists a N 0 and a positive constant k such that
f ( n ) k log log n ,   n N 0
Since log log n log n for sufficiently large n, there must exist a N 1 such that
f ( n ) k log n ,   n N 1
thus f ( n ) = O ( log n )
mafalexpicsak

mafalexpicsak

Beginner2022-10-15Added 4 answers

This is because, if n is large enough, | f | K log ( log n ) for some constant K and log x x for all x
More generally, if f = O ( g ) and g = O ( h ) then f = O ( h ) ( O ( O ( h ) ) = O ( h )

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?