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

<ul>
<li>any deterministic algorithm takes linear time;</li>
<li>there is a Las Vegas randomized algorithm with sublinear expected running time.</li>
</ul>

CC BY-SA 3.0
2012-09-20T18:35:26.253Z
2012-09-20T18:35:26.253Z
someone
<p>Title pretty much explains the question. E.g. </p>

<p><a href="http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm</a></p>

<p>Should there in theory also be an algorithm with guaranteed runtime that is also linear? </p>

<p>Not looking for a response to this specific case necessarily, but more generally.</p>

<p>Thanks all. </p>

CC BY-SA 3.0
2012-09-20T14:45:51.557Z
Please learn Las Vegas algorithms and complexity class ZPP.  The answer to your question depends on what you allow as error.
Tsuyoshi Ito
<cc.complexity-theory>
For a given algorithm with expected runtime M, does there exist (in theory) an algorithm with equivalent guaranteed runtime?
Graham
# For a given algorithm with expected runtime M, does there exist (in theory) an algorithm with equivalent guaranteed runtime?

(Asked by: username_0 on 2012-09-20)

Title pretty much explains the question. E.g.

<http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm>

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.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: Please learn Las Vegas algorithms and complexity class ZPP.  The answer to your question depends on what you allow as error.  

---

## 1 answers

### Answer by username_2 on 2012-09-20. Score: 5 | Accepted answer

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.


---

