1
$\begingroup$

Here is a divide and conquer approach for finding minimum and maximum elements in an array.

MaxMin(i, j, max, min)
{  
   //max and min are the references so that we can retain their value when
   //we return from the function. i and j are the indices of start and 
   //end respectively.
     if (i=j) then max := min := a[i]; //Small(P)
      else if (i=j-1) then // Another case of Small(P)
      {
            if (a[i] < a[j]) then max := a[j]; min := a[i];
            else max := a[i]; min := a[j];
      }
     else
     {
           // if P is not small, divide P into sub-problems.
           // Find where to split the set.
           mid := ( i + j )/2;
           // Solve the sub-problems.
           MaxMin( i, mid, max, min );
           MaxMin( mid+1, j, max1, min1 );
           // Combine the solutions.
           if (max < max1) then max := max1;
           if (min > min1) then min := min1;
    }

}

If we analyze the complexity of this algorithm, we see that if n is the power of 2, then it does (3n/2)-2 comparisons. My question is how many comparisons does it do if n is not an exact power of 2. I think it does more than 3n comparisons because at the base level, we are left with 3 elements(which take 3 comparisons) instead of 2 elements(which take just 1 comparison). But I am not sure about my thinking. Any help would be appreciated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.