Comparing 1024 numbers - Part 2

I got this same problem (generalized for $n$ numbers) in my algorithms class. Here's my solution submitted for that problem. Suppose that the numbers are integers, just so that I won't write the awkward "number of numbers".

---

We claim that we need $2n-2 - \left\lfloor \frac{n}{2} \right\rfloor$ comparisons.

For each integer, we give it two flags: possibleMax and possibleMin , indicating that the number is still possible to be the maximum and minimum respectively. On a comparison, we remove the possibleMin flag from the greater integer and the possibleMax flag from the lesser integer, if they exist, as the greater integer can no longer be the minimum and the lesser integer can no longer be the maximum. Our objective is to get only one possibleMax flag and one possibleMin flag.

Consider two integers. If they both have both flags present, then a comparison knocks off two flags. Call such comparison good . However, if at least one flag is missing, in the worst case we might only be able to remove one flag. Clearly any comparison cannot remove more than two flags. Thus the number of comparisons needed is the number of flags, subtracted by two (the actual maximum integer retains its possibleMax flag, and the minimum retains its possibleMin ), subtracted by the number of good comparisons. The number of flags is fixed, $2n$ , but the number of good comparisons can vary, denote it as $k$ .

Call an integer that has both flags present pure . Note that every good comparison requires two pure integers; if either integer involved is not pure, then it's possible that the comparison only removes one flag, thus making it not a good comparison. Also note that every good comparison reduces the number of pure integers by two, and there is no way to get an integer from not pure to being pure again. Thus the number of good comparisons is capped above by $\left\lfloor \frac{n}{2} \right\rfloor$ ; there are $n$ pure integers, and a good comparison takes $2$ .

Thus, as $k \le \left\lfloor \frac{n}{2} \right\rfloor$ , we need $2n-2-k \ge 2n-2-\left\lfloor \frac{n}{2} \right\rfloor$ comparisons to complete our objective. This can be achieved: pair off all the integers, dividing them into "greater" and "lesser" set depending on the outcome of their comparisons. This probably leaves one element unpaired; include it in both sets. Then simply find the maximum among the greater integers and the minimum among the lesser integers. The first pairing takes $\left\lfloor \frac{n}{2} \right\rfloor$ comparisons; finding maximum of greater integers takes $\left\lfloor \frac{n+1}{2} \right\rfloor - 1$ comparisons (there are $\left\lfloor \frac{n+1}{2} \right\rfloor$ integers, and each comparison removes one candidate at best); finding minimum of lesser integers also takes $\left\lfloor \frac{n+1}{2} \right\rfloor - 1$ comparisons (consider the negations of the integers and find its maximum), totaling the given $2n - 2 - \left\lfloor \frac{n}{2} \right\rfloor$ comparisons. Thus our bound is the best possible.

Substituting $n=1024$ , this gives $2 \cdot 1024 - 2 - \left\lfloor \frac{1024}{2} \right\rfloor = 2046 - 512 = \boxed{1534}$ comparisons.

First, we have 1024 numbers. Divide it into 512 pairs..and check which is smaller and which is larger. After doing this we have two set :

1.Larger : all 512 bigger numbers

2.Smaller : all 512 smaller numbers

Now we know that the bigger one lies in the set Larger because if it lies in the set Smaller then it must have been smaller than some number. Similarly, the smaller number lies in the set Smaller .

To find the bigger number in the set Larger we require minimum 511 comparisons. (Refer to my solution here ) . Similarly we require minimum 511 comparisons to find the smaller number from the set Smaller .

Hence, minimum number of comparisons is 512+511+511 = 1534