Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

No Minimum-Time Algorithm?

  1. May 26, 2009 #1
    I was just wondering. Is there a computational problem P for which there is no asymptotically least-time solution?

    In other words: let x be an algorithm which is a solution to P. Denote by T(x), the worst-case runtime of x as a function of its input size. Is it possible that for any algorithm x that solves P, there exists an algorithm y that solves P, where T(y) = o(T(x))?

    o is little-o notation, so in other words that would mean T(y) = O(T(x)) and T(y) is not Θ(T(x)).
  2. jcsd
  3. Jan 10, 2011 #2
    Well, there are algorithms that take time O(ln(x)). Does that count? You just want something that is faster than linear, or do you want something that isn't asymptotic to ANYthing? What are you after? O(ln(ln(ln .... forever .... (x)))))....)? That wouldn't even make any sense. Take the log enough times and eventually you get a negative number, and you take it again, and poof.
    holy cow, I didn't notice what date this was written. The thing just showed me a bunch of related posts and I was perusing them.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook