Повторный логарифм сложности Big-O

Question

У меня 2 сомнения:

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,

Даже без учета факториала экспоненциальная башня должна расти намного быстрее, чем мощность.