such that subsequences and have size at least / and at most / eachotherwisea call is "bad nowconsider the implications of our choosing pivot uniformly at random note that there are / possible good choices for the pivot for any given call of size of the randomized quick-sort algorithm thusthe probability that any call is good is / note further that good call will at least partition list of size into two lists of size / and / and bad call could be as bad as producing single call of size now consider recursion trace for randomized quick-sort this trace defines binary treetsuch 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 ( / )in 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 (lognthereforethe total expected running time of randomized quick-sort is (nlogn(see figure figure visual time analysis of the quicksort tree each node is shown labeled with the size of its subproblem