Randomized Algorithms & Randomized Quicksort

(i) Randomized Algorithms (as in Q59)

Algorithms using random bits to make decisions; behavior probabilistic. Las Vegas always correct, running time random (e.g., Randomized QuickSort, Skip List). Monte Carlo may be incorrect with bounded probability (e.g., Miller-Rabin). Usage: avoid adversary, simple, expected guarantees.

(ii) Randomized Quicksort Algorithm

RandomizedQuicksort(A, low, high):
  if low < high:
    p = RandomizedPartition(A, low, high) // random pivot
    RandomizedQuicksort(A, low, p-1)
    RandomizedQuicksort(A, p+1, high)

RandomizedPartition(A, low, high):
  i = Random(low, high)  // uniform
  swap A[i], A[high]
  return Partition(A, low, high) // Lomuto/Hoare as in Q14

Alternative: pick random pivot internally without swap.

(iii) Time Complexity

• Worst-case still $Θ(n^2)$ but probability extremely low (requires always bad pivot). No adversary can force it (random pivot independent of input order).
• Expected (over random choices) $Θ(n \log n)$ for any input. Proof: expected partition splits balanced on average; linearity of expectation over comparisons → $E[T(n)] = 2/n \sum_{k} E[T(k)] + Θ(n)$ solves to $Θ(n\log n)$.
• Best $Θ(n\log n)$.
• Space $O(\log n)$ expected stack depth.

Randomization converts worst-case $O(n^2)$ on sorted input (deterministic pivot last) into expected $O(n\log n)$ universally.