Can someone help me find a relationship in terms of O, o, Ω, ω, or Ɵ between the two functions lg(lg*(n)) and (2lg*n)?
Suppose f(n) = log*(n)
. Now, we should compare log(f(n))
and 2^f(n)
. Hence, it should be straightforward to show that log(f(n)) = o(2^f(n))
. The o
in the notation is little-o
. As 2^f(n)
grows exponentially and log(f(n))
grows logarithmically. You should notice that f(n)
is a monotonic increasing function.