Software Journal

#cs6212gwu – Spring 2011 – HW1 – Q4

This is a common puzzle.  Given an array of n sorted numbers, how to find BOTH the minimum and the maximum using as few comparisons as possible.  If only the minimum (or the maximum) is to be found, then that can be done by using n-1 comparisons.  So, the first algorithm could be to find the minimum, and then to find the maximum from the remaining, in a total of (n-1) + (n-2) comparisons.

A better algorithm is that we first compare pairs of numbers (in n/2) comparisons, and collect n/2 “winners” and n/2 “losers”.  Then, find the maximum from the winners, in n/2 – 1 comparisons, and the minimum from the losers in n/2 – 1. That is a total of 3n/2 – 2 comparisons.

So much is straightforward. Much more interesting question arises, if we ask:

Is the algorithm presented above optimal?  In other words, can we say that any algorithm that is based on comparisons will need at least 3n/2 – 2 comparisons, regardless of in which sequence it does the comparisons.

We want to prove that for any given algorithm (let us call it algorithm A), there is a sequence of numbers for which A takes at least 3n/-2 comparisons to find both the maximum and minimum numbers.  Such a proof can be constructed based on adversary (or game theoretic approach); essentially saying that an adversary will actively work against the algorithm to maximize the number of comparisons needed, but with the condition that the adversary cannot contradict itself.  For example, adversary cannot say a > b, b > c and then also say c > a.

Adversary thinks in terms of numbers in 4 buckets:

• Bucket Q – contains numbers that have never been compared to anything yet.
• Bucket W – Contains numbers that have only won games that they have played.  So, they are candidates for being the maximum.
• Bucket L – Contains numbers that have only lost games that they have played.  So, they are candidates for being the minimum.
• Bucket X – Contains numbers that have both won and lost games they have played.  So, they are not candidates for being the minimum or the maximum.

These buckets start with the following state when the algorithm A starts:

Bucket Q: n numbers, Buckets W, L, X: 0 numbers each.

Finally, when algorithm A finishes, this must be the state:

Bucket Q: 0 numbers; Bucket W: 1 number; Bucket L: 1 number; Bucket X: n-2 numbers

Adversary goes by the following rules for creating outcomes of comparisons:

• C1: When comparing two numbers in bucket Q – one number will go into W bucket, and one number will go into L bucket.  (Net change: -2, +1, +1, 0)
• C2: When comparing a number from W bucket to a number from Q bucket, the number  from W will win and will remain in W.  Number from Q bucket will go into L.  (Net change -1,0,+1,0)
• C3: When comparing a number from L bucket to a number from Q bucket, the number  from L will lose and will remain in L.  Number from Q bucket will go into W.  (Net change -1,+1,0,0)
• C4: When comparing a number from W bucket to a number from X bucket, the number  from W will win and will remain in W.  Number from X bucket will remain in X.  (Net change 0,0,0,0)
• C5: When comparing a number from L bucket to a number from X bucket, the number  from L will lose and will remain in L.  Number from X bucket will remain in X.  (Net change 0,0,0,0)
• C6: When comparing a number from W bucket to a number from L bucket, the number  from L will lose and will remain in L.  Number from W bucket will remain in W.  (Net change 0,0,0,0)
• C7: When comparing two numbers from W bucket, one will remain in W, and one will go into X.  (Net change, 0, -1, 0, +1)
• C8: When comparing two numbers from L bucket, one will remain in L, and one will go into X.  (Net change, 0, 0, -1, +1)

These rules ensure the following points:

• Maximum of 2 numbers can be removed from Q bucket during each comparison, and during this comparison, no number goes into the X bucket.   [This happens in comparison C1.]
• During each comparison, maximum of 1 number can enter the X bucket.  [This happens in comparisons C7, C8, and in those comparisons, there is no change in the size of the Q bucket.]

So, we observe that we need n-2 comparisons (of type C7/C8) simply to fill up the X bucket (we need n-2 numbers there by the end).  Further, since those comparisons do not involve Q bucket, we need at least additional n/2 comparisons just to empty out the Q bucket (it starts with n numbers and needs to have 0 numbers).  So, in total, we need to make at least 3n/2 – 2 comparisons just to make sure Q and X buckets have the desired state before algorithm A can draw its conclusions.

QED.