sort. If the partitioning is unbalanced, however, it can run asymptotically as slowly as insertion sort. In this section, we shall informally investigate how quicksort performs under the assumptions of balanced versus unbalanced partitioning. Worst-case partitioning The worst-case behavior for quicksort occurs when the partitioning routine produces one subproblem with n1 elements and one with 0 elements. (We prove this claim in Section 7.4.1.) Let us assume that this unbalanced partitioning arises in each recursive call. The partitioning costs (n) time. Since the recursive call on an array of size 0 just returns, T(0)=(1), and the recurrence for the running time is T(n)=T(n1)+T(0)+(n)=T(n1)+(n). Intuitively, if we sum the costs incurred at each level of the recursion, we get an arithmetic series (equation (A.2)), which evaluates to (n2). Indeed, it is straightforward to use the substitution method to prove that the recurrence T(n)= T(n1)+(n) has the solution T(n)=(n2). (See Exercise 7.2-1.) Thus, if the partitioning is maximally unbalanced at every recursive level of the algorithm, the running time is (n2). Therefore the worst-case running time of quicksort is no better than that of insertion sort. Moreover, the (n2) running time occurs when the input array is already completely sorted-a common situation in which insertion sort runs in O(n) time. Best-case partitioning In the most even possible split, PARTITION produces two subproblems, each of size no more than n/2, since one is of size n/2 and one of size n/21. In this case, quicksort runs much faster. The recurrence for the running time is then T(n)=2T(n/2)+(n), where we tolerate the sloppiness from ignoring the floor and ceiling and from subtracting 1. By case 2 of the master theorem (Theorem 4.1), this recurrence has the solution T(n)=(nlgn). By equally balancing the two sides of the partition at every level of the recursion, we get an asymptotically faster algorithm. Balanced partitioning The average-case running time of quicksort is much closer to the best case than to the worst case, as the analyses in Section 7.4 will show. The key to understand- 7.2I Use the substitution method to prove that the recurrence T(n)=T(n1)+(n) has the solution T(n)=(n2), as claimed at the beginning of Section 7.2