I am trying to improve my mmA method such that the number of comparisons is 3n/2

Question

I am trying to improve my mmA method such that the number of comparisons is 3n/22. the method I attach below only give me the number of comparison is 2+C(n/2)+C(n/2). My improved method must still take into parameter ( int lowerBound, int upper bound , int [] array) and must still be recursive- no loops. please help, thank you

public class MinMax {
  
  
public static void main(String[] args) {
int[] array = new int[]{4, 7, 2, 10, 345, 28, 1, 5, 0, -10, -4098, 23, 0};

Pair expected = new Pair(-4098, 345);
Pair actual = MinMax.mmB(0, array.length-1, array);
if (actual.alpha != expected.alpha) {
System.out.println("Min value incorrect. Expected: "+expected.alpha+" but got: "+actual.alpha);
} else if (actual.omega != expected.omega) {
System.out.println("Max value incorrect. Expected: "+expected.omega+" but got: "+actual.omega);
} else {
System.out.println("Test Passed"+actual.alpha +" "+ actual.omega);
}
}

public static Pair mmA(int lB, int uB, int[] array){
if (uB == lB){
return new Pair(array[lB], array[uB]);
}
else if (uB - lB == 1) {
int smallest = Math.min(array[lB], array[uB]);
int largest = Math.max(array[lB], array[uB]);
return new Pair(smallest, largest);
}
else {
int mid = (lB + uB)/2;
Pair First = mmA(lB, mid, array);
Pair Next = mmA(mid+1, uB, array);
int smallest = Math.min(First.alpha, Next.alpha);
int largest= Math.max(First.omega, Next.omega);
return new Pair(smallest, largest);
}
}

Explanation / Answer

See the below updated method will take the time complexcity of 1.5n-2 for number of comparisions..see the updated code below..

public static Pair mmA(int lb, int uB, int[] arrayay)
{
       Pair result = new Pair();
       Pair left = new Pair();
       Pair right = new Pair();

       // if there is only one element
       if (lb == uB) {
           result.max = array[lb];
           result.min = array[lb];
           return result;
       }

       // if there are two elements
       if (uB == lb + 1) {
           if (array[lb] > array[uB]) {
               result.max = array[lb];
               result.min = array[uB];
           } else {
               result.max = array[uB];
               result.min = array[lb];
           }
           return result;
       }

       // if there are more than 2 elements
       int mid = (lb + uB) / 2;
       left = getMinMax(array, lb, mid);
       right = getMinMax(array, mid + 1, uB);

       if (left.min < right.min)
           result.min = left.min;
       else
           result.min = right.min;

       if (left.max > right.max)
           result.max = left.max;
       else
           result.max = right.max;

       return result;  
}

# of Comparisons:

T(1) = 0
T(2) = 1
T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2 ~ 2(T(n/2) + 2 = 1.5n -2

this below updated logic for mmA will take comparision complexity like 1.5n-2.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.