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)=\left \{ O(1) if n=1or 2 \right \}

           \left \{ 2T(n/2)+c if n>2 \right \}

 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)

 

 

 

0Comment