running time of quick-sort we can analyze the running time of quick-sort with the same technique used for merge-sort in section namelywe can identify the time spent at each node of the quick-sort tree and sum up the running times for all the nodes examining code fragment we see that the divide step and the final concatenation of quick-sort can be implemented in linear time thusthe time spent at node of is proportional to the input size (vof vdefined as the size of the sequence handled by the invocation of quick-sort associated with node since subsequence has at least one element (the pivot)the sum of the input sizes of the children of is at most ( let si denote the sum of the input sizes of the nodes at depth for particular quick-sort tree clearlys nsince the root of is associated with the entire sequence alsos < since the pivot is not propagated to the children of more generallyit must be that si si- since the elements of the subsequences at depth all come from distinct subsequences at depth and at least one element from depth does not propagate to depth because it is in set (in factone element from each node at depth does not propagate to depth iwe can therefore bound the overall running time of an execution of quick-sort as ( hwhere is the overall height of the quick-sort tree for that execution unfortunatelyin the worst casethe height of quick-sort tree is th( )as observed in section thusquick-sort runs in ( worst-case time paradoxicallyif we choose the pivot as the last element of the sequencethis worst-case behavior occurs for problem instances when sorting should be easy--if the sequence is already sorted given its namewe would expect quick-sort to run quicklyand it often does in practice the best case for quick-sort on sequence of distinct elements occurs when subsequences and have roughly the same size in that caseas we saw with merge-sortthe tree has height (log nand therefore quick-sort runs in ( log ntimewe leave the justification of this fact as an exercise ( - more sowe can observe an ( log nrunning time even if the split between and is not as perfect for exampleif every divide step caused one subsequence to have one-fourth of those elements and the other to have three-fourths of the elementsthe height of the tree would remain (log nand thus the overall performance ( log nwe will see in the next section that introducing randomization in the choice of pivot will makes quick-sort essentially behave in this way on averagewith an expected running time that is ( log