selection algorithm that runs in (nworst-case time the existence of this deterministic algorithm is mostly of theoretical interesthoweversince the constant factor hidden by the big-oh notation is relatively large in this case suppose we are given an unsorted sequence of comparable elements together with an integer [ ,nat high levelthe quick-select algorithm for finding the kth smallest element in is similar in structure to the randomized quicksort algorithm described in section we pick an element from at random and use this as "pivotto subdivide into three subsequences leand gstoring the elements of less than xequal to xand greater than xrespectively this is the prune step thenbased on the value of kwe then determine which of these sets to recur on randomized quick-select is described in code fragment algorithm quickselect( , )inputsequence of comparable elementsand an integer [ ,noutputthe kth smallest element of if then return the (firstelement of pick random (pivotelement of and divide into three sequences*lstoring the elements in less than *estoring the elements in equal to *gstoring the elements in greater than if <=|lthen quickselect( ,kelse if <| |ethen return {each element in is equal to xelse quickselect( , | -| |{note the new selection parameteranalyzing randomized quick-select showing that randomized quick-select runs in (ntime requires simple probabilistic argument the argument is based on the linearity of expectationwhich states that if and are random variables and is numberthen ( )= ( )+ (yand (cx)=ce( )where we use (zto denote the expected value of the expression let (nbe the running time of randomized quick-select on sequence of size since this algorithm depends on random eventsits running timet( )is random variable we want to bound ( ( ))the expected value of (nsay that recursive invocation of our algorithm is "goodif it partitions so that the size of and is at most / clearlya recursive call is good with probability / let (ndenote the number of consecutive recursive calls we makeincluding the present onebefore we get good one then we can characterize (nusing the following recurrence equationt( )<=bn* (nt( / )where > is constant applying the linearity of expectation for we get ( ( )<= (bn* (nt( / )=bn* ( ( ) ( ( / )since recursive call is good with probability / and whether recursive call is good or not is independent of its parent call being goodthe expected value of (