[TECH] Finding max and min in exactly 3n/2-2 Element Comparisions.

We know that the lower bound on the minimum number of comparisons to find max
and min in an array of n. In fact the recurrence T(n) = 2T(n/2)+2
solves exactly to 3n/2-2 the following is an interesting way to find max
and min in exactly 3n/2-2 comparisons non-recursively(assume ‘n’ is even). Also note by comparison we mean the element comparisons as they are significant.

current_min = a[0]; current_max=a[1];
/* 1 comparison here */
if(current_min < current_max){
  current_min = a[1]; current_max = a[0];
}
/*(n-1)-2+1 times*/
for(i=2;i<n-1;i+=2){
  /*3 Element Comparisons here */
  if(a[i] < a[i+1]){
      if(a[i] < current_min) current_min = a[i];
      if(a[i+1] > current_max) current_max = a[i+1];
  }else{
      if(a[i+1] < current_min) current_min = a[i+1];
      if(a[i] > current_max) current_max = a[i];
  }
}
/*return current_max current_min*/

Analysis: Total Comparisions = 1 + (((n-1)-2+1)/2)*3 = 3*n/2-2.

~ by Vamsi Kundeti on March 1, 2008.