比较lg（lg * n）和2 ^（lg * n）的渐近符号大哦，小哦哦，ω，Ɵ

Question

有人可以帮助我证明“n的日志星的日志”（lg（lg *（n）））和“n的日志星的2次幂”（2lg * n）之间的关系。

FYI日志位于基数2。

Answer 1

假设f(n) = log*(n)。现在，我们应该比较log(f(n))和2^f(n)。因此，显示log(f(n)) = o(2^f(n))应该是直截了当的。符号中的o是little-o。随着2^f(n)呈指数级增长，log(f(n))以对数方式增长。你应该注意到f(n)是一种增加单调的功能。