Answer and Explanation:
Note that we are free to use any data structure that allows for arbitrary insertion and deletion of data
As an underlying data structure, we’ll use an (unsorted) array. INSERT(S, x) will simply append x to the array, increasing its length. This has a constant runtime, so we’ll say its cost is 1.
DELETE-LARGER-HALF(S) will work as follows: first, use SELECT to find the median. Next, use PARTITION around the median to make sure that the upper half is stored within the last elements. Finally, we delete these elements, reducing the size of the array.This has a linear running time, so we’ll say its cost is n.
To show that any m operations can run in O(m) time, we define a potential function . The amortized cost of INSERT is thus
; the amortized cost of DELETE-LARGER-HALF is
. So the amortized cost of any m operations is O(m).
This answer essentially captures the idea behind the problem. However, there are some technical points to clear up. (Calling the real-time costs 1 and n are not among them; this underestimates the running time by at most a constant. Ignoring constants like that is necessary to make concise arguments about amortized costs.)
First, an array does not support arbitrary insertions. Possible remedies include:
(1) using a dynamic array along the lines of §17.4, or (2) using a different structure like a linked list, and having DELETE-LARGER-HALF convert it to an array and back in linear time so that the SELECT and PARTITION algorithms may be used.
Second, it’s important to know which median to partition around and how to delete the upper half of the elements: a mistake could lead to incorrect behavior when the array has an odd size or repeated elements. We should select the lower median,, since that’s the number of elements we want in the lower set: as written, the CLRS Partition function will put elements less than or equal to the
pivot in the left set, and strictly larger elements in the right set. (If the partition function is defined differently, the answer should be different as well. You generally should give a brief description of how your partition function works.) After a call to Partition, it is safe simply to keep the first elements and drop the rest. On the other hand, it is not safe to go around deleting every element with
a sufficiently large value—take an array of zeros as a drastic example. If you wish to take that approach, you’ll have to count the number of elements equal to the median and delete the correct number of them.
Finally, the argument only shows that the <em>amortized</em> cost with respect to is O(m). The conclusion we’re asked for requires a technical condition: the potential
never drops below its initial value. This is true for the usual reason: initially,
= 0 because S is empty; during execution,
by definition.