Title pretty much explains the question. E.g.


Should there in theory also be an algorithm with guaranteed runtime that is also linear?

Not looking for a response to this specific case necessarily, but more generally.

Thanks all.

  • 2
    $\begingroup$ Please learn Las Vegas algorithms and complexity class ZPP. The answer to your question depends on what you allow as error. $\endgroup$ – Tsuyoshi Ito Sep 20 '12 at 14:45

No. See Chapter 2 of the book Randomized Algorithms by Motwani and Raghavan. They discuss a tree-evaluation problem for which:

  • any deterministic algorithm takes linear time;
  • there is a Las Vegas randomized algorithm with sublinear expected running time.
| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.