Randomized Algorithms
Randomized Algorithms: An algorithm that uses random numbers to decide what to do next anywhere in its logic is called a Randomized Algorithm . For example , in Randomized Quick Sort, we use a random number to pick the next pivot (or we randomly shuffle the array) Type of Randomized Algorithms 1. Las Vegas: A Las Vegas algorithm is an algorithm which uses randomness, but gives guarantees that the solution obtained for given problem is correct. Advantage: Always produce a correct answer. Randomness affects the running time, not correctness. Expected running time is finite and analyzed probabilistically. A randomized quick-sort algorithm where we randomly choose pivot is an example of Las-Vegas algorithm. The algorithm always sorts the array. The advantage we get with randomization is, there is no pattern for which the quick sort causes worst case (unlike choosing fixed pivot like a corner element causes wor...