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:

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.

Post a Comment