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}) $