59. Probabilistic Algorithms and Randomized Quick Sort

Probabilistic algorithms introduce randomness to achieve either better average performance or simplify the algorithm structure. There are two main types:

1. Las Vegas Algorithms: Always produce the correct result, but their running time is random (e.g., Randomized Quick Sort).
2. Monte Carlo Algorithms: May produce an incorrect result with some probability, but their running time is deterministic (e.g., Bloom Filters, covered in Lesson 30).

Randomized Quick Sort

We know that the worst case for Quick Sort is O(N²), which happens when the pivot selection is consistently bad.

Solution: Instead of always choosing the first or last element as the pivot, choose the pivot randomly from the subarray.

• Impact: While the theoretical worst-case remains O(N²), the probability of that worst case ever occurring in practice becomes astronomically low. The algorithm's expected time complexity is O(N log N), regardless of the input array's organization.