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 \{i \ge 0 : f^{(i)}(n) \le c \}$ 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)$.

$$ \begin{array}{ccl} f(n) & c & {f_c}^* \\ \hline 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 & \text{does not converge} \\ n^{1 / 3} & 2 & \Theta(\log_3{\lg n}) \\ n / \lg n & 2 & \omega(\lg\lg n), o(\lg n) \end{array} $$