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 ? ?, we define the iterated function f^*_c by

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) f;(n) . 1 b. Ig n c. /2 1 d. /2 2 e. f. g. 1/3 h. /1gn 2. 2.