algorithmmathcomplexity-theory

Compare lg(lg* n) and 2^(lg*n ) asymptotically


Can someone help me find a relationship in terms of O, o, Ω, ω, or Ɵ between the two functions lg(lg*(n)) and (2lg*n)?


Solution

  • 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.