Consider a randomly chosen function $f(n)$ over positive integers ($n$) such that $n \leq ceil(f(n))$. How do we prove that:

For any such chosen $f(n)$: There always exists a problem $P$ such that: The most efficient algorithm for $P$ has the worst case running time of $f(n)$.

We are assuming a standard Universal Turing Machine model as a reference/foundation.

New contributor
xyz is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • 1
    $\begingroup$ I did not downvote, but I assume that it is because you juste stated a problem without context and expected the community to solve it for you without sharing your thoughts or explaining your difficulties in solving it. $\endgroup$
    – Nathaniel
    Nov 22 at 20:48
  • $\begingroup$ Please edit the question to explain the context: where did you see this claim? why do you think it is true? what is the motivation? I am skeptical whether it is true. See, for example, en.wikipedia.org/wiki/Constructible_function, math.stackexchange.com/q/51082/14578 $\endgroup$
    – D.W.
    Nov 22 at 22:02


Your Answer

xyz is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.