Большая тета итеративного логарифма

Question

У меня есть две математические функции: log (log * n) и 2 ^ (log * n). Теперь я хочу вычислить асимптотический рост этих двух функций (особенно я хочу найти большую тета). Наконец, я хочу сравнить их сложность. Может ли кто-нибудь поделиться формальным / интуитивным решением, которое может решить такие проблемы?

Благодарю.

Answer 1

Это интересно. Начнем со стандартной техники: сложно рассуждать об экспонентах, поэтому давайте возьмем их логарифмы и посмотрим, что произойдет. Это оставляет нам следующие функции:

log (log(log* n)) и log * n.

Теперь вопрос в том, как они соотносятся друг с другом. Вообще говоря, журнал некоторой функции всегда будет расти медленнее, чем сама функция, при условии, что функция продолжает расти по мере увеличения. Используя тот факт, что log k 2^222, мы получим это log* n ≥ 4, поэтому log log* n ≥ 2, поэтому log log log* n ≤ log* n, что дает нам log log log* n = O(log* n). Отсюда нетрудно показать, что log log * n = O(2^{log* n}).