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 2022-10-13 Answered
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.
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (2)

getrdone07tl
Answered 2022-10-14 Author has 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 )
Did you like this example?
Subscribe for all access
mafalexpicsak
Answered 2022-10-15 Author has 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 )
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2022-06-03
How do i solve this equation of e?
The problem is to solve for x in
e 2 x + 2 e x 15 = 0
the book's answer is x = ln ( 3 )
can anyone show how they got this answer? thanks!
asked 2022-07-07
Prove that log 2 5 + log 2 7 > log 12
What I tried so far:
log 2 5 + log 2 7 > log 3 + log 4
( log 5 + log 7 ) 2 2 log 5 log 7 > log 3 + log 4
But it seems that I'm not even near the result.
Every suggestion / hint would be appreciated :)
Thanks in advance.
EDIT: log means log 10
asked 2022-06-20
Changing base of a logarithm by taking a square root from base?
From my homework I found
log 9 x = log 3 x
and besides that an explanation that to this was done by taking a square root of the base. I fail to grasp this completely. Should I need to turn log 9 x into base 3, I'd do something like
log 9 x = log 3 x log 3 9 = log 3 x log 3 3 2 = log 3 x 2
but this is a far cry from what I've given as being the correct answer.
Substituting some values to x and playing with my calculator I can see that the answer given as correct is correct whereas my attempt fails to yield the correct answer.
Now the question is, what are correct steps to derive log 3 x from log 9 x ? How and why am I allowed to take a square root of the base and the exponent?
asked 2021-12-30
What is ln(ex)?
asked 2022-06-11
Integrating ln ( x ) × ln ( 1 x )
Is there a way I can derive the value of the integral
0 1 ln ( x ) ln ( 1 x ) d x
using the fact that
i = 1 1 n 2 = π 2 6
? (the actual value of the integral is 2 π 2 6 )
Thanks in advance
asked 2022-03-29
Prove the inequality exxe for x>0
asked 2021-11-10
Solve the equation.
ln(4x)+ln3=ln(2x)

New questions