Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|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

 
discard

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

Browse other questions tagged or ask your own question.