Problem 3.6
Iterated functions
We can apply the iteration operator $*$ used in the $\lg^*$ function to any monotonically increasing function $f(n)$ over the reals. For a given constant $c \in \mathbb{R}$, we define the iterated function $f_c^*$ by
$$ f_c^*(n) = min \lbrace i \geq 0 : f^{(i)}(n) \leq c \rbrace $$
which need not be well defined in all cases. In other words, the quantity $f_c^*(n)$ is the number of iterated applications of the function $f$ required to reduce its argument down to $c$ or less.
For each of the following functions $f(n)$ and constants $c$, give as tight a bound as possible on $f_c^*(n)$.
| $ f(n) $ | $ c $ | $ f_c^*(n) $ |
|---|---|---|
| $ n - 1 $ | $ 0 $ | $ \Theta(n) $ |
| $ \lg{n} $ | $ 1 $ | $ \Theta(\lg^*{n}) $ |
| $ n / 2 $ | $ 1 $ | $ \Theta(\lg{n}) $ |
| $ n / 2 $ | $ 2 $ | $ \Theta(\lg{n}) $ |
| $ \sqrt{n} $ | $ 2 $ | $ \Theta(\lg\lg{n}) $ |
| $ \sqrt{n} $ | $ 1 $ | does not converge |
| $ n^{1/3} $ | $ 2 $ | $ \Theta(\log_3{\lg{n}}) $ |
| $ n/\lg{n} $ | $ 2 $ | $ \omega(\lg\lg{n}), o(\lg{n}) $ |