chap7-solutions

Solution to Exercise7.2-3

P ARTITION does a“worst-case partitioning”when the elements are in decreasing

order.It reduces the size of the subarray under consideration by only1at each step,

which we’ve seen has running time?.n2/.

In particular,P ARTITION,given a subarray A?p::r of distinct elements in de-

creasing order,produces an empty partition in A?p::q 1 ,puts the pivot(orig-

inally in A?r )into A?p ,and produces a partition A?p C1::r with only one

fewer element than A?p::r .The recurrence for Q UICKSORT becomes T.n/D

T.n 1/C?.n/,which has the solution T.n/D?.n2/.