SKEDSOFT

where we are considering whether the comparison takes place at any time during the execution of the algorithm, not just during one iteration or one call of PARTITION. Since each pair is compared at most once, we can easily characterize the total number of comparisons performed by the algorithm:

Taking expectations of both sides, and then using linearity of expectation and Lemma 5.1, we obtain

It remains to compute Pr {z_i is compared to z_j}.

It is useful to think about when two items are not compared. Consider an input to quicksort of the numbers 1 through 10 (in any order), and assume that the first pivot element is 7. Then the first call to PARTITION separates the numbers into two sets: {1, 2, 3, 4, 5, 6} and {8, 9, 10}. In doing so, the pivot element 7 is compared to all other elements, but no number from the first set (e.g., 2) is or ever will be compared to any number from the second set (e.g., 9).

In general, once a pivot x is chosen with z_i < x < z_j, we know that z_i and z_j cannot be compared at any subsequent time. If, on the other hand, z_i is chosen as a pivot before any other item in Z_ij, then z_i will be compared to each item in Z_ij, except for itself. Similarly, if z_j is chosen as a pivot before any other item in Z_ij, then z_j will be compared to each item in Z_ij , except for itself. In our example, the values 7 and 9 are compared because 7 is the first item from Z_7,9 to be chosen as a pivot. In contrast, 2 and 9 will never be compared because the first pivot element chosen from Z_2,9 is 7. Thus, z_i and z_j are compared if and only if the first element to be chosen as a pivot from Z_ij is either z_i or z_j.

We now compute the probability that this event occurs. Prior to the point at which an element from Z_ij has been chosen as a pivot, the whole set Z_ij is together in the same partition. Therefore, any element of Z_ij is equally likely to be the first one chosen as a pivot. Because the set Z_ij has j - i 1 elements, the probability that any given element is the first one chosen as a pivot is 1/(j - i 1). Thus, we have

The second line follows because the two events are mutually exclusive. Combining equations (7.2) and (7.3), we get that

We can evaluate this sum using a change of variables (k = j - i) and the bound on the harmonic series in equation (A.7):

Thus we conclude that, using RANDOMIZED-PARTITION, the expected running time of quicksort is O(n lg n).