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).

Transcribed Image Text:

f (n) f;(n) а. п—1 b. Ig n c. п/2 1 d. п/2 2 e. f. л g. п1/3 h. п/1gn 2. 2.