How many comparisons are required?

Question

Let $S$ be a set of $n$ integers. Assume you can perform only addition of elements of $S$ and comparisons between sums. Under these conditions how many comparisons are required to find the maximum element of $S$?

I thought that we could find the maximum element as followed:

    max=S(1)+S(1)
    k=1
    for j=2 to n
         sum=S(1)+S(j)
         if sum>max
               max=sum
               k=j
    return S(k)

That means that $n-1$ comparisons are required.

Is this correct??

Answer 1

The find-max algorithm is pretty standard. I'm not sure why you are using addition operations at all. They are unnecessary.

The algorithm works as follows:

findMax(array arr) 
     max := 0

     for i = 1 to arr.length - 1
        if arr[i] > arr[max]
            max := i

     return arr[max]

This algorithm uses exactly $n-1$ comparisons.

Answer 2

To prove $n-1$ is a lower bound, you can make a tree structure. The leaves are the integers. Each comparison links the two elements compared and produces a parent that is the greater. Until you have done $n-1$ the tree cannot have all the leaves, so you don't know which is the greatest. You need to show that addition can't help.

Answer 3

The following argument shows that you need at least $n-1$ comparisons. Suppose that the algorithm only needs $n-2$ (or less) comparisons. Let us simulate it under the assumption that all comparisons end with the result "equal". This gives us $n-2$ equations on the $n$ variables, and so a solution space of dimension 2. The solution space must contain a non-constant vector $v$. In particular, both $v$ and $-v$ are possible solutions, but they have different maximal elements.

To illustrate this bound, let us trace the standard algorithm mentioned by ml0105. The first $n-2$ comparisons give us the equations $a_1 = a_2 = \cdots = a_{n-2} = a_{n-1}$. The solution space is spanned by the vectors $\vec{1} = [1\;1\;\cdots\;1]$ and $v = [0\;0\;\cdots\;0\;1]$. Both $v$ and $-v$ are solutions, but under $v$ only $a_n$ is maximal, while under $-v$ only $a_n$ is not maximal. The final comparison eliminates $v$ from the solution space, and the argument breaks down since the solution space consists only of constant vectors, and so all elements are maximal.