Asymptotic Growth Rate

Suppose we are given three pegs and $n$ disks, with all $n$ disks having different size. Initially, the $n$ disks are stacked in decreasing size, from bottom to top, in the first peg (see Figure 6.1). The Tower of Hanoi problem is to transfer the entire tower of $n$ disks from the first peg to the second peg, moving one disk at a time and never putting a larger disk on top of a smaller disk. What is the fastest solution to this problem? Is the fastest solution feasible for size $n=64$ (the size of the original Tower of Hanoi problem)?

Figure 6.1: The Tower of Hanoi problem.

Show that the function $2^{\sqrt{\log n}}$ grows slower than every function in the polynomial sequence, but faster than every function in the poly-log sequence.

Suppose $f(n) \prec g(n)$. Show that there exists a function $h(n)$ such that $f(n) \prec h(n) \prec g(n)$.

Show that $\log^{*} n \prec \log^{(m)} n$ for any constant integer $m \geq 1$.

Show that $2^{\ln n}=o(n)$ and $2^{\log (2 n)}=O(n)$.

Show that $(\log n)^{10} \prec n^{10} \prec 2^{(\log n)^{10}}$.

Compare the following three functions using the $\prec$ notation:

Compare $2^{\log { }^{*} n}$ with $n$ using the $\prec$ notation.

Suppose that $f(n) \prec g(n)$. Is it true that for any increasing function $h(n)$ with $\lim_{n \rightarrow \infty } h(n)=\infty , h(f(n)) \prec h(g(n))$? Present a proof or a counterexample.

Prove that $\log^{(k+1)} \prec \log^{(k)} n$ for any $k \geq 0$.

Denote $\log^{* *} n=\min \left\{ k \mid \left(\log^{*}\right)^{(k)} n \leq 1, k \geq 1\right\}$. Compare $\log^{* *} n$ with $\log^{*} n$.

Recall the Ackermann function $A$ defined in Exercise 8 of Section 4.8.