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];
           // 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.


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.