Finding Big Theta

Question

I am in a Data Structures and Algorithms class. I am trying to indicate if f(n) is Big Theta of g(n). I will also have to indicate Big O, small o, etc... but I am lost about the way to approach this particular pair.

f(n) = log* (log n)
g(n) = log( log* n )

From what I have currently learned, if this pair completes this statement

Θ(g(n))={f(n):there exists c_1, c_2 > 0 and n_0 <br>
 such that 0 ≤ c_1 g(n) ≤ f(n) ≤ c_2 g(n) for all n ≥ n_0}.

My problem is that I have no idea what log * is and how to use it.

Answer 1

I have no idea what log * is

Well, look it up. Unfortunately, Google doesn't search for symbols too well, but Googling log star turns up the iterated logarithm immediately, and SymbolHound, a search engine that doesn't ignore symbols, turns up a StackOverflow post explaining it. It's also probably in your book or course notes somewhere.

The iterated logarithm, denoted log*(n), is the number of times you need to take the logarithm of n before you get a value less than or equal to 1.

To solve the problem, consider the following. If you need to take the logarithm of n log*(n) times before you get a value <= 1, how many times do you need to take the logarithm of log(n) to do the same thing?