[Solved]: Classfication of randomized algorithms

Problem Detail: 

From Wikipedia about randomized algorithms

One has to distinguish between algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time, and probabilistic algorithms, which, depending on the random input, have a chance of producing an incorrect result (Monte Carlo algorithms) or fail to produce a result (Las Vegas algorithms) either by signalling a failure or failing to terminate.

1. I was wondering how the first kind of "algorithms use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time?
2. What differences are between it and Las Vegas algorithms which may fail to produce a result?
3. If I understand correctly, probabilistic algorithms and randomized algorithms are not the same concept. Probabilistic algorithms are just one kind of randomized algorithms, and the other kind is those use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time?

Asked By : Tim

Answered By : Luke Mathieson

1. An example of such an algorithm is randomized Quick Sort, where you randomly permute the list or randomly pick the pivot value, then use Quick Sort as normal. Quick Sort has a worst case running time of $O(n^{2})$, but on a random list has an expected running time of $O(n\log n)$, so it always terminates after $O(n^{2})$ steps, but we can expect the randomized instance to terminate after $O(n\log n)$ steps, always with a correct answer.

2. This gives an subset of Las Vegas algorithms. Las Vegas algorithms also allow for the possibility that (with low probability) it may not terminate at all - not just terminate with a little bit more time.

3. These in turn are really just a type of Monte Carlo algorithm, where the answer can be incorrect (with low probability), which is at least conceptually different to maybe not answering.

There's a whole bunch of detail I've left out of course, you might want to look up the complexity classes ZPP, RP and BPP, which formalise these ideas.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6221