Randomized

Definition

A randomized algorithm is an algorithm that introduces an element of randomness or uncertainty during its execution.

Instead of producing a deterministic result for a given input, a randomized algorithm may yield different outcomes on different runs due to the use of random inputs or coin flips.

Randomized algorithms are often employed to achieve efficiency, simplicity, or improved average-case performance compared to deterministic counterparts.

Examples

Examples include algorithms for approximate counting, Monte Carlo simulations, and certain graph algorithms that use randomization for better efficiency or faster convergence.

Quick select

QuickSelect is a randomized algorithm for finding the k-th smallest element in an unordered list. It is closely related to the QuickSort algorithm and is based on the partitioning technique. QuickSelect works by selecting a pivot element, partitioning the list into two parts, and then recursively focusing on the part that contains the desired element until the element is found. The random choice of the pivot contributes to the average-case linear time complexity, making QuickSelect efficient for finding specific elements in an unsorted list.