Improving finding Min and Max in Array

Question

my teacher taught me Flash Sort Algorithms, which costs about O(n). Before running that sort, I have to find out which the elements are maximum and minimum in the array.

This is my solution:

//n is a size of array a[]
for(int i = 0; i < n ; i++){
  if (_max < a[i]) _max = a[i];
  if (_min > a[i]) _min = a[i];
}

Let f(n) is a number of conditional operator in that for-loop (excepts comparing variable i). So it costs:

• n time for comparing _max with a[i]
• n time for comparing _min with a[i]

So, f(n) = 2n.

My friend wrote a code like this:

for(int i = 0; i < n-1; i+=2)
  if (a[i] < a[i+1]){
    if (_max < a[i+1]) _max = a[i+1];
    if (_min > a[i]) _min = a[i];
  }
  else{
    if (_max < a[i]) _max = a[i];
      if (_min > a[i+1]) _min = a[i+1];
  }
// Compare one more time if n is odd
if (n % 2 == 1){
  if (_min > a[n-1]) _min = a[n-1];
  if (_max < a[n-1]) _max = a[n-1];
}

We can easily get f'(n) = 3n/2 + 3. It seems that f'(n) < f(n) when n is large enough.

But my teacher requires that f(n) = n or f(n) = n + a, with a is a const.

Are there any ideas?

Answer 1

No. It is impossible to find both maximum and minimum value in exactly n(or n+a) comparisons. It will need at least 3n/2 - 2 comparisons. See this proof and this proof. Maybe you can show these proofs to your teacher...

Are there any other hints about the sequence? Like it's uniformly distributed or such?