MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$$ ?


share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.