is atmosts( given quick-sort tree tlet denote the sum of the input sizes of the nodes at depth in clearlys nsince the root of is associated with the entire sequence alsos < since the pivot is not propagated to the children of consider next if both children of have nonzero input sizethen otherwise (one child of the root has zero sizethe other has size ) thuss < continuing this line of reasoningwe obtain that < as observed in section the height of is in the worst case thusthe worstcase running time of quick-sort is by proposition which is that isthusquick-sort runs in ( worst-case time given its namewe would expect quick-sort to run quickly howeverthe quadratic bound above indicates that quick-sort is slow in the worst case paradoxicallythis worst-case behavior occurs for problem instances when sorting should be easy--if the sequence is already sorted going back to our analysisnote that the best case for quick-sort on sequence of distinct elements occurs when subsequences and happen to have roughly the same size that isin the best casewe have - ( si