0
$\begingroup$

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!

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.