Сравните lg (lg * n) и 2 ^ (lg * n) в терминах асимптотической записи big-Oh, small-Oh Ω, ω, Ɵ

Question

Может кто-нибудь помочь мне доказать связь между «log of log star of n» (lg (lg * (n))) и «2 power of log star of n» (2 ^{lg * 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) - монотинная возрастающая функция.