## Friday, February 29, 2008

### [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.

#### 1 comment:

Anonymous said...

hey, I think you hava a mistake in the second line:
"if(current_min < current_max)...
it should be >, isn't??
thank for the algorithm, I needed for a homework.