In class, we have seen the following randomized selection algorithm:

Algorithm RSelect$($S$,$ k$)$:

Input: Sequence S of numbers, integer k with $1<=|$S$|<=$ k

Output: k$-$th smallest number in S

if $|$S$|=1$

then return the only element in S

else p $=$ uniformly random element in S;

by scanning S and making $|$S$|1$ comparisons, divide it into

S$<=\{$x in S : x $<$ p$\},$

S$==\{$x in S : x $=$ p$\},$

S$>=\{$x in S : x $>$ p$\}$;

if k $<=|$S$<|$

then RSelect$($S$<,$ k$)$

else if k $>=1+|$S$<|+|$S$=|$

then RSelect$($S$>,$ k $|$S$<||$S$=|)$

else return p

endif

endif

endif

Let T be the random variable whose value is the number of comparisons made by this

algorithm. With n denoting the length of the sequence S$,$ we have shown that the expected

value of T is O$($n$).$