# Repeated function resulting in quadratic time.

Let $$r(f, x) = k$$ such that

$$f^k (x) < 2 \hbox{ and } f^{k-1} (x) \geq 2$$

For example $$r(n \rightarrow n-1, 2^n) = 2^n-1; r(n \rightarrow n/2, 2^n) = n.$$

For an arbitrary $c$, we have $$r( n \rightarrow n/2^{1/c}, 2^n) = cn$$.

Question, for an arbitrary $c$, is there some closed form function $f$ such that

$$r(f, 2^n) = n^c$$ ?

Thanks!

-
Title refers to "quadratic time", body doesn't. Que? –  Gerry Myerson Oct 20 '11 at 23:27
Maybe the asker is thinking of the specific case where $r(f,2^n) = n^2$? –  mhum Oct 21 '11 at 1:28
Maybe. But it's asker's job to post a clear, unambiguous question, not our job to guess what asker means. –  Gerry Myerson Oct 21 '11 at 5:08
The answer is: "Yes, there is such a function". –  Igor Rivin Oct 21 '11 at 12:02