Асимптотический темп роста

Пусть даны три стержня и $n$ дисков, причём все $n$ дисков имеют разный размер. Изначально $n$ дисков сложены в порядке убывания размера, снизу вверх, на первом стержне (см. рис. 6.1). Задача о Ханойской башне состоит в том, чтобы перенести всю башню из $n$ дисков с первого стержня на второй, перемещая по одному диску за раз и никогда не кладя больший диск на меньший. Каково самое быстрое решение этой задачи? Является ли самое быстрое решение практически осуществимым при размере $n=64$ (размере исходной задачи о Ханойской башне)?

Рис. 6.1: задача о Ханойской башне.

Покажите, что функция $2^{\sqrt{\log n}}$ растёт медленнее любой функции полиномиальной последовательности, но быстрее любой функции полилогарифмической последовательности.

Пусть $f(n) \prec g(n)$. Покажите, что существует функция $h(n)$, такая что $f(n) \prec h(n) \prec g(n)$.

Покажите, что $\log^{*} n \prec \log^{(m)} n$ для любого фиксированного целого $m \geq 1$.

Покажите, что $2^{\ln n}=o(n)$ и $2^{\log (2 n)}=O(n)$.

Покажите, что $(\log n)^{10} \prec n^{10} \prec 2^{(\log n)^{10}}$.

Сравните следующие три функции с помощью обозначения $\prec$:

Сравните $2^{\log { }^{*} n}$ и $n$ с помощью обозначения $\prec$.

Пусть $f(n) \prec g(n)$. Верно ли, что для любой возрастающей функции $h(n)$ с $\lim_{n \rightarrow \infty } h(n)=\infty$ выполняется $h(f(n)) \prec h(g(n))$? Приведите доказательство или контрпример.

Докажите, что $\log^{(k+1)} \prec \log^{(k)} n$ для любого $k \geq 0$.

Обозначим $\log^{* *} n=\min \left\{ k \mid \left(\log^{*}\right)^{(k)} n \leq 1, k \geq 1\right\}$. Сравните $\log^{* *} n$ и $\log^{*} n$.

Вспомните функцию Аккермана $A$, определённую в упражнении 8 раздела 4.8.