CLRS, Problems 3 Part 2

Problems3.md

Problems 3-3

In descending order.

1. $2^{\lg^* n}$
2. $\lg^* n$
3. $\lg (\lg^* n)$

We consider ${\sqrt 2}^{\lg n}$. Let's compare it with $2^{\lg^* n}$. We conjecture that the first is greater than the second. We have:

$$ \begin{align} 2^{\lg^* n} &\lt {\sqrt 2}^{\lg n} \\ 2^{\lg^* n} &\lt {2^{1/2}}^{\lg n} \\ \end{align} $$

Suppose $n = 2000$. Let $c_1 = \lg n$. We have:

$$ \begin{align} 2^{\lg^* n} &\lt {\sqrt 2}^{\lg n} \\ 2^{4} &\lt {2^{1/2}}^{c_1} \\ 2^{4} &\lt 2^{{c_1}/2} \\ 4 &\lt \frac{1}{2}{c_1} \\ \end{align} $$

Which is true as $n$ and $c_1$ grow.