Week 5
CS2107: Design and Analysis of Algorithms
Randomized Algorithms
Dr. Eiman Alharby
Department of Computer Science and Artificial Intelligence
Umm Al-Qura University
Disclaimer: Materials are based on Dr. Manal Alharbi’s course & original course by DR. Rajasekaran, Sultan Almuhammadi, and other references
Previously …
• Master Theorem gives a shortcut to solve divide-and-conquer recurrences of the form
𝑛
𝑇 𝑛 = 𝑎𝑇 + 𝑓 𝑛 , 𝑎 ≥ 1 and 𝑏 > 1 by comparing cost at the root vs. leaves.
𝑏
• Divide-and-Conquer paradigm:
– Divide problem → Conquer subproblems recursively → Combine results.
• Applications:
– Binary Search: 𝑇 𝑛 = 𝑇 𝑛/2 + 𝑂 1 ⇒ 𝑂 log 𝑛 .
– Quick Sort: Average case 𝑂 𝑛 log 𝑛 ,worst case 𝑂 𝑛2 ; in-place.
• Matrix Multiplication:
– Classical/Recursive: 𝑂 𝑛3 .
– Strassen: 7 multiplications → 𝑂 𝑛2.81 ,space 𝑂 𝑛2 .
• Big picture:
– Divide-and-conquer enables more efficient algorithms by breaking problems down.
– Time efficiency often improves, but space costs and stability must also be considered.
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 2
Agenda
• Introduction to Randomised Algorithms
– Why Randomness in Algorithms?
– Types of Randomised Algorithms
• Case Study: Randomised Quicksort
– Randomised Quicksort algorithm, expected runtime, comparison of pivot choice strategies
• Randomised Selection (Quickselect)
– Recursive Quickselect, time complexity analysis, common mistakes
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 3
What is randomized algorithm?
• Randomized algorithm is a different design approach taken by the standard
algorithms where few random bits are added to a part of their logic.
• It incorporates random choices into their logic to improve efficiency, simplify design,
or handle worst-case inputs more effectively.
• They are different from deterministic algorithms; deterministic algorithms follow a
definite procedure to get the same output every time an input is passed where
randomized algorithms produce a different output every time they are executed.
• It is important to note that it is not the input that is randomized, but the logic of the
standard algorithm
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 4
Why Randomness in Algorithms? (1/2)
Deterministic tie-breaking = predictable behaviour → adversarial or
1. Breaking ties and symmetry unlucky inputs can systematically trigger worst-case runtime.
– In many problems, deterministic tie-breaking can lead to worst-case inputs.
– Randomization ensures that ties or repeated structures don’t systematically hurt performance.
– Example: In Quicksort, always picking the first element as pivot gives O(n²) on sorted arrays,
where a random pivot avoids this bias.
Randomized tie-breaking = unpredictable behaviour → adversary
can’t force bad cases, and expected runtime is much better.
2. Avoiding adversarial inputs
– Randomization makes the behaviour unpredictable, so adversaries cannot consistently force
bad cases.
– Example: Hash functions with randomization reduce collisions in practice.
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 5
Why Randomness in Algorithms? (2/2)
3. Reducing complexity
– Some problems are computationally expensive deterministically but much faster with
randomness.
– Randomized approximation algorithms often yield “good enough” answers much faster.
– Example: Approximate counting, randomized rounding in optimization, randomized min-cut in
graphs.
4. Simplicity and practicality
– Sometimes randomized algorithms are easier to implement and run faster on average than
their deterministic counterparts.
– Example: Randomized load balancing with “power of two choices” in distributed systems.
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 6
Two Types of Randomized Algorithms
1. Las Vegas Algorithms
– Always produce the correct answer.
– Runtime varies depending on random choices.
– Example: Randomised Quicksort (correctly sorts, runtime distribution depends on pivots).
– Key metric: Expected running time.
2. Monte Carlo Algorithms
– Always run in a bounded time, but the answer may be incorrect with a small probability.
– Key metric: Probability of error (can be reduced by repetition).
– Often used when approximate answers are acceptable or when error probability can be made
tiny.
– These algorithms are used for solving physical simulation system and mathematical system.
Las Vegas = correct but variable runtime.
Monte Carlo = fast runtime but small probability of error.
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 7
Randomized Quicksort Algorithm
• Randomized quick sort is designed to decrease the chances of the algorithm being
executed in the worst case time complexity of O(n2).
• The worst case time complexity of quick sort arises when the input given is an
already sorted list, leading to n(n ) comparisons. There are two ways to randomize
the quicksort
– Randomly shuffling the inputs: Randomization is done on the input list so that the sorted
input is jumbled again which reduces the time complexity. However, this is not usually
performed in the randomized quick sort, because it increases the space complexity.
– Randomly choosing the pivot element: Making the pivot element a random variable is
commonly used method in the randomized quick sort. Here, even if the input is sorted, the
pivot is chosen randomly so the worst case time complexity is avoided.
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 8
Randomized Quicksort Algorithm
Review of Deterministic Quicksort Randomization Principle
• Idea: Pick a pivot → partition into two subarrays • Problem with deterministic choice: Input order
→ recursively sort them. can “trick” the algorithm into its worst case.
• Partition step complexity: 𝑂(𝑛) • Solution: Pick pivot randomly.
• Worst case: • Randomness ensures that the pivot is equally
– If pivot is always the smallest/largest element, likely to be any of the n elements.
partitions are maximally unbalanced. • Effect:
– Recurrence: 𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑂(𝑛) = 𝑂(𝑛²) – Balanced partitions become probable.
– Example: Already sorted array with first-element – Consistently unbalanced partitions become
pivot rule. exponentially unlikely.
• Best case:
– Pivot splits array exactly in half each time.
– Recurrence: 𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑂(𝑛) = 𝑂(𝑛 log 𝑛)
• Average case: ~𝑂(𝑛 log 𝑛) but depends on pivot
strategy.
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 9
Randomized Quicksort Algorithm
ALG RandQuickSort(A, low, high): Expected Runtime Analysis
if low < high: • Key random variable: position of the pivot at each
i = RANDOM(low, high) # Pick random pivot recursion step.
swap A[i] with A[high] # Move pivot to end • At each call, pivot is equally likely to split the array
p = Partition(A, low, high) anywhere.
RandQuickSort(A, low, p-1) • Expected number of comparisons over the entire
run:
RandQuickSort(A, p+1, high)
𝐸𝐶 𝑛 =2 𝑃(elements 𝑖 & 𝑗 are compared)
1≤𝑖<𝑗≤𝑛
2
• Partition(A, low, high): Rearranges array so that • 𝑃 elements 𝑖 & 𝑗 are compared = 𝑗−𝑖+1
elements ≤ pivot are on left, > pivot are on right.
Runs in O(n). • So: 𝐸 𝐶 𝑛 = 𝑂 𝑛 log 𝑛
• Intuition:
– Each element is compared only a logarithmic number of
times on average.
– Random pivot avoids consistent imbalance.
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 10
Quicksort: Comparison of Pivot Choice Strategy
Pivot Choice Worst Case Average Case Notes
Bad if input is
First element 𝑂(𝑛²) 𝑂(𝑛 log 𝑛)
sorted/reverse-sorted.
Same problem as first
Last element 𝑂(𝑛²) 𝑂(𝑛 log 𝑛)
element.
Often better in practice, but
Median-of-three 𝑂(𝑛2 ) 𝑂(𝑛 log 𝑛)
not adversarially robust.
O(n²) worst, O(n log n) Robust against adversarial
Random element
expected input.
Note: Even randomised Quicksort can hit 𝑂(𝑛²), but with probability so low that expected runtime is much closer to
𝑂(𝑛 log 𝑛).
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 11
Randomized Quickselect Algorithm
• The Randomized Quickselect algorithm is a selection algorithm used to find the k-th
smallest element in an unsorted array.
• It is closely related to the QuickSort algorithm but focuses on partitioning only the
relevant part of the array, making it more efficient for this specific task.
• The algorithm operates by selecting a random pivot element, partitioning the array
around the pivot, and then determining which part of the array contains the k-th
smallest element.
• It recursively processes only the relevant partition, reducing the average time
complexity to O(n). However, the worst-case complexity remains O(n²).
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 12
Randomized Selection (Quickselect)
• Problem: Find the 𝑘-th smallest element in ALG Quickselect(A, low, high, k):
an unsorted array. if low==high: return A[low]
• Algorithm: if low < high:
– Randomly pick pivot. i = RANDOM(low, high)
– Partition.
swap A[i] with A[high]
– Recurse only into the side contains the 𝑘 -th
element p=Partition(A, low, high)
• Expected runtime: 𝑂(𝑛) if k==p: return A[p]
• Worst-case: 𝑂(𝑛2 ) (rare due to elif k<p: Quickselect(A, low, p-1, k)
randomization). else: Quickselect(A, p+1, high, k)
• Application: median finding, order statistics,
data sampling. Practice: Find 4th smallest element (k=3):
2 3 1 9 7 6 10 5
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 13
Quickselect: Time Complexity Analysis
• Let 𝑇(𝑛) be the runtime of Quickselect algorithm on any input of size 𝑛.
• Then we have:
𝑇(𝑛) = 𝑛 + max{𝑇(|𝑋1|), 𝑇(|𝑋2|)}.
• Worst case happens when one of the parts is empty on each recursive call. Hence:
𝑇(𝑛) = 𝑛 + 𝑇(𝑛 − 1) which solves to: 𝑇(𝑛) = Θ(𝑛2).
• Best case is when both 𝑋1 and 𝑋2 are of nearly the same size. In this case:
𝑛
𝑇(𝑛) = 𝑂(𝑛) + 𝑇 = Θ(𝑛).
2
• We can also show that the expected runtime of quick select is 𝑂(𝑛).
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 14
Quickselect: Common Mistakes
• Off-by-one on k.
– Decide 0-based or 1-based and stick to it everywhere.
• Wrong k semantics.
– In this version, k is global index. Don’t convert to “rank within subarray”.
• Not randomizing pivot.
– Deterministic first/last pivot can degrade to 𝑂 𝑛2 on nearly sorted data.
• Slicing arrays.
– Keep (low,high) indices to avoid extra space/time, and don’t create new arrays like: left =
arr[:pivot], right = arr[pivot+1:]
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 15
Quickselect: Common Mistakes
• Ignoring duplicates.
– If the array has many equal elements: Standard 2-way partition (< pivot and > pivot) becomes
inefficient and recursion may not shrink properly.
– Better approach: Use 3-way partition:
• < pivot
• == pivot
• > pivot
– This handles duplicates efficiently and avoids unnecessary recursion.
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 16
Why Randomized Approaches Win in Practice
• Simplicity
– shorter code, fewer edge-cases.
• Speed
– better expected performance; excellent constants (randomised Quicksort, hashing).
• Adversarial robustness
– random pivot/hash defeats worst-case inputs.
• Scalability
– naturally parallel (independent trials), streaming-friendly (Bloom, sketches).
• Tunable guarantees
– pick rounds/bits to hit a target error 𝛿.
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 17
Key Takeaways
• Randomness breaks symmetry and thwarts adversarial/worst-case inputs while
keeping code simple and fast in expectation.
• Las Vegas vs Monte Carlo: Today’s algorithms (Randomized Quicksort, Quickselect)
are Las Vegas
– always correct; only runtime is random.
• Randomized Quicksort: same as Quicksort; pivot chosen uniformly at random each
call.
– Expected comparison = 𝐸 𝐶 𝑛 = Θ(𝑛 log 𝑛)
– Random pivoting neutralizes sorted/reverse inputs that doom deterministic first/last-pivot
variants.
• Recursive Quickselect: identical partition step to Randomized Quicksort; recurse on
one side only based on 𝑘 vs pivot index 𝑞.
– Expected time = 𝐸 𝑇 𝑛 = Θ 𝑛
– Worst case is 𝑂 𝑛2 but occurs with vanishing probability under random pivots.
Dr. Eiman Alharby CS2107: Design and Analysis of Algorithms 18