Sorting algorithms - Data Structures and Problem Solving Using Java - page 370

throwing out constant factors and solve this recurrence by telescoping
Equation 8.1 repeatedly:

TN () = TN 1 ( - ) + N

TN 1 ( - ) = TN 2 ( - ) + ( N 1 - )

TN 2 ( - ) =

…

TN 3 ( - ) + ( N 2 - )

(8.2)

T 2 () = T 1 () + 2

When we add everything in Equation 8.2, we obtain massive cancellations,
yielding

NN 1 ( + )

---------------------- ON 2

T () = T () +++ + 23… N = = ()

(8.3)

2

This analysis verifies the intuition that an uneven split is bad. We spend
N units of time to partition and then have to make a recursive call for N - 1
elements. Then we spend N - 1 units to partition that group, only to have to
make a recursive call for N - 2 elements. In that call we spend N - 2 units
performing the partition, and so on. The total cost of performing all the par-
titions throughout the recursive calls exactly matches what is obtained in
Equation 8.3. This result tells us that, when implementing the selection of
the pivot and the partitioning step, we do not want to do anything that might
encourage the size of the subsets to be unbalanced.

average case

The first two analyses tell us that the best and worst cases are widely different.
Naturally, we want to know what happens in the average case. We would
expect that, as each subproblem is half the original on average, the O ( N log N )
would now become an average-case bound. Such an expectation, although cor-
rect for the particular quicksort application we examine here, does not consti-
tute a formal proof. Averages cannot be thrown around lightly. For example,
suppose that we have a pivot algorithm guaranteed to select only the smallest
or largest element, each with probability 1/2. Then the average size of the
small group of elements is roughly , as is the average size of the large
group of elements (because each is equally likely to have 0 or elements).
But the running time of quicksort with that pivot selection is always quadratic
because we always get a poor split of elements. Thus we must carefully assign
the label average. We can argue that the group of small elements is as likely to
contain 0, 1, 2, , or elements, which is also true for the group of large
elements. Under this assumption we can establish that the average-case run-
ning time is indeed O ( N log N ).

The average case
is O ( N log N )
Although this
seems intuitive, a
formal proof is
required.

N 2 ⁄

N 1 -

… N 1 -