Quicksort and
Randomized Algs
Design and Analysis
CS-854 Advanced of Algorithms
Algorithm Analysis
Lecture 11
How can we avoid the worst
case?
l Inject randomness into the data
What is the running time of
randomized Quicksort?
l Worst case?
O(n2)
l Still could get very unlucky and pick “bad”
partitions at every step
randomized Quicksort:
expected running time
l How many calls are made to Partition for an input of
size n? n
l What is the cost of a call to Partition?
l Cost is proportional to the number of iterations of the
for loop
the total number of
comparisons will give
us a bound on the
running time
Counting the number of
comparisons
l Let zi of z1, z2,…, zn be the i th smallest
element
l Let Zij be the set of elements Zij= zi, zi+1,…, zj
A = [3, 9, 7, 2]
z1 = 2
z2 = 3 Z24 =
z3 = 7
z4 = 9
Counting the number of
comparisons
l Let zi of z1, z2,…, zn be the i th smallest
element
l Let Zij be the set of elements Zij= zi, zi+1,…, zj
A = [3, 9, 7, 2]
z1 = 2
z2 = 3 Z24 = [3, 7, 9]
z3 = 7
z4 = 9
Counting comparisons
(indicator random variable)
l How many times can zi be compared to zj?
l At most once. Why?
Total number of
comparisons
Counting comparisons:
average running time
expectation of sums is the sum of
expectations
remember,
?
l The pivot element separates the set of numbers into
two sets (those less than the pivot and those larger).
Elements from one set will never be compared to
elements of the other set
l If a pivot x is chosen zi < x < zj then how many times
will zi and zj be compared?
l What is the only time that zi and zj will be
compared?
l In Zij, when will zi and zj will be compared?
?
p(a,b) = p(a)+p(b) for
independent events
pivot is chosen
randomly over j-i+1
elements
E[X] ?
Let k = j-i
Bound on Harmonic series A.7
Randomized algorithms
l We used randomness to minimize the
possibility of worst case running time
l Other uses
l approximation algorithms, i.e. random walks
l initialization, e.g. K-means clustering
l contention resolution
l reinforcement learning/interacting with an ill-
defined world
