now consider recursion trace for randomized quick-sort this trace defines binary treet such that each node in corresponds to different recursive call on subproblem of sorting portion of the original list say that node in is in size group if the size of ' subproblem is greater than ( / ) + and at most ( / ) let us analyze the expected time spent working on all the subproblems for nodes in size group by the linearity of expectation (proposition )the expected time for working on all these subproblems is the sum of the expected times for each one some of these nodes correspond to good calls and some correspond to bad calls but note thatsince good call occurs with probability / the expected number of consecutive calls we have to make before getting good call is moreovernotice that as soon as we have good call for node in size group iits children will be in size groups higher than thusfor any element from in the input listthe expected number of nodes in size group containing in their subproblems is in other wordsthe expected total size of all the subproblems in size group is since the nonrecursive work we perform for any subproblem is proportional to its sizethis implies that the total expected time spent processing subproblems for nodes in size group is (nthe number of size groups is log / nsince repeatedly multiplying by / is the same as repeatedly dividing by / that isthe number of size groups is (log nthereforethe total expected running time of randomized quick-sort is ( log (see figure if factwe can show that the running time of randomized quick-sort is ( log nwith high probability (see exercise - number of size groups size group (rs(as(bsize group (log ns(cs(ds(eexpected time per size group (nsf size group (no(ntotal expected timeo( log nfigure visual time analysis of the quick-sort tree each node is shown labeled with the size of its subproblem