迭代对数Big-O复杂度

Question

我有两个疑问: -

1)是(log*n)^ n = O((logn)!)？

2)哪个更大,log(log*n)或log*(logn)？

Answer 1

对于2),你有log*(log n) = log*(n)-1.然后让m = log*(n).你有m-1 > log(m)足够大的m.

提示:

对于1),让m = log*(n).然后LHS是m^n,并且RHS是指数高度塔的对数m的阶乘,即指数高度塔的阶乘m-1.

即使忽视阶乘,指数塔也应该比动力增长得快得多.