analyzing 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 ( + ( ( and (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 each of and is at most / clearlya recursive call is good with probability at least / 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 at least / and whether recursive call is good or not is independent of its parent call being goodthe expected value of (nis at most the expected number of times we must flip fair coin before it comes up "heads that ise( ( )< thusif we let (nbe shorthand for ( ( ))then we can write the case for as ( < ( / bn to convert this relation into closed formlet us iteratively apply this inequality assuming is large sofor exampleafter two applicationst ( < (( / ) ( / ) bn at this pointwe should see that the general case is log / nt ( < bn ( / ) = in other wordsthe expected running time is at most bn times geometric sum whose base is positive number less than thusby proposition (nis (nproposition the expected running time of randomized quick-select on sequence of size is ( )assuming two elements of can be compared in ( time