For a given algorithm with expected runtime M, does there exist (in theory) an algorithm with equivalent guaranteed runtime? 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.
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.