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