Max-Min algorithm

Max-Min is an application of Divide and Conquer.

Input -An array of n-element

output: Finding the maximum and minimum of an array

Let 'a' is an array name contain n elements

let 'i' is a variable contain  first element index and  variable 'j' last element index

let max and min used to hold maximum and minimum value

Algo:

DAC-CON(a, i,j)

{

if(i==j)

{

max=min=a[i];

return(max,min)

}

if (i==j-1)

{

if(a[i]>a[j])

{

max=a[i];

min=a[j];

}

else

{

min=a[i];

max=a[j];

}

return (max,min)

}

else

{

mid=(i+j)/2;

(max1,min1)=DAC-CON(a,i, mid);

(max2,min2)=DAC-CON(a,mid+1,j);

if(max1>max2)

{

max=max1;

}

else

{

max=max2;

}

if(min1>min2)

{

min=min2;

}

else

{

min=min1;

}

return(max,min)

}

}

Let T(n) be the time complexity of the above program on 'n' elements then

Recurrence relation:

T(n)=

after Apply master theorem   we get O(n) time complexity

And the  number of comparisons between the elements for above program on 'n' array element is (3*n/2)