From Wikipedia about randomized algorithmsOne 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.I was wondering how the first kind of algorithms use the randominput to reduce the expected running time or memory usage, butalways  terminate with a correct result in a bounded amount of time?What differences are between it and Las Vegas algorithms which mayfail to produce a result?If I understand correctly,  probabilistic algorithms and randomized algorithms are not the same concept. Probabilistic algorithms are just onekind of randomized algorithms, and the other kind is those use therandom  input to reduce the expected running time or memory usage,but always  terminate with a correct result in a bounded amount oftime?
Classfication of randomized algorithms
algorithms;terminology;randomized algorithms;nondeterminism;machine models
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.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.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.