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(n)\) by

\[f^*_c(n) = \min \{ i \geq 0 : f^{(i)}(n) \leq 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 possible on \(f^*_c(n)\).

\[\newcommand\T{\Rule{0pt}{.5em}{.5em}} \begin{array}{|c|c|c|c|} \hline & f(n) & c & f^*_c(n) \\\hline \textbf{a.} & \T n-1 & \T 0 & \T \Theta(n) \\\hline \textbf{b.} & \T \lg n & \T 1 & \T \Theta(\lg^* (n)) \\\hline \textbf{c.} & \T n / 2 & \T 1 & \T \Theta(\lg(n)) \\\hline \textbf{d.} & \T n / 2 & \T 2 & \T \Theta(\lg(n)) \\\hline \textbf{e.} & \T \sqrt{n} & \T 2 & \T \Theta(\lg(\lg(n))) \\\hline \textbf{f.} & \T \sqrt{n} & \T 1 & \T \text{no solution} \\\hline \textbf{g.} & \T n^{1/3} & \T 2 & \T \Theta(\log_3(\lg(n))) \\\hline \textbf{h.} & \T n / \lg(n) & \T 2 & \T \Omega(\lg(n) / \lg(\lg(n))) \\\hline \end{array}\]

c. and d. evaluate out to \(\lg (n) + 1\) and \(\lg (n)\) respectively, both of which are bound by \(\Theta(\lg(n))\)

In order to solve e. suppose we have some integer \(m_i\) which is found in the sequence \(\{2, 4, 16, 256, ... \}\). This can be written as \(\{2^{2^0}, 2^{2^1}, 2^{2^3},... \}\) so then \(m_i = 2^{2^i}\). The smallest \(m_i\) that is greater than or equal to \(n\) suggests that our solution to \(f^*_c(n) = i\) because we must apply \(\sqrt{n}\) to \(n\) \(i\) times before our result is \(\leq 2\). Handily, \(\lg(\lg(n)) = i\) works because \(n = 2^{2^i}\) as well, therefore \(\Theta(\lg(\lg(n)))\) is a tight bound for our solution.

f. has no solution because we cannot reach \(1\) by square-rooting an integer (unless that integer is also \(1\)).

We can solve g. by using similar logic. Suppose we have some integer \(p_i\) which is found in the sequence \(\{2, 8, 512, (134,217,728), ... \}\) = \(\{2^{3^0}, 2^{3^1}, 2^{3^2},... \}\) so then \(p_i = 2^{3^i}\). The smallest \(p_i\) that is greater than or equal to \(n\) suggests our solution to \(f^*_c(n) = i\). In order to account for the exponent term change, we tweak our solution to be \(\log_3(\lg(n)) = i\) which applies here because \(n = 2^{3^i}\), therefore \(\Theta(\log_3(\lg(n))\) is a tight bound for our solution.

h. does not neatly calculate out into an equation that is a tightly bound, and \(\Omega(\lg(n) / \lg(\lg(n)))\) is one of the only possible solutions I found that comes close as a representation of this function’s \(f^*_c\).