time-complexity - 迭代对数 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。

即使不考虑阶乘，指数塔的增长速度也应该比幂快得多。