Answer:
Check the explanation
Explanation:
Program for Max and Min:
1.)
public class Max_Min {
static Max_Min m=new Max_Min();
static int local_max,local_min;
public static void main(String ar[])
{
int a[]={101,112,191,17,115,111,10};
Max_Min.local_max=Max_Min.local_min=a[0];
int[] get_Max_Min=m.Max_Min(a, 0, a.length-1, a[0], a[0]);
System.out.println("Max : "+get_Max_Min[0]+"\nMin : "+get_Max_Min[1]);
}
public int[] Max_Min(int[] a,int i,int j,int local_max,int local_min)
{
int mid,max1,min1;
int result[]=new int[2];
if (i==j) { local_max = local_min = a[i]; }
else if (i==j-1)
{
if (a[i] < a[j]) { this.local_max = get_Max(this.local_max,a[j]); this.local_min = get_Min(this.local_min,a[i]); }
else { this.local_max = get_Max(this.local_max,a[i]); this.local_min = get_Min(this.local_min,a[j]); }
}
else
{
mid = ( i + j )/2;
// Solve the sub-problems.
max1=min1=a[mid+1];
Max_Min( a, i, mid, local_max, local_min );
Max_Min( a, mid+1, j, max1, min1 );
// Combine the solutions.
if (this.local_max < max1) this.local_max = max1;
if (this.local_min > min1) this.local_min = min1;
}
result[0]=this.local_max; result[1]=this.local_min;
return result;
}
public static int get_Max(int i,int j)
{
if(i>j) return i;
else return j;
}
public static int get_Min(int i,int j)
{
if(i>j) return j;
else return i;
}
}
2. Finding complexity:
When n is a power of two, n = 2k
-WHERE k is positive integer
T(n) = 2T(n/2) + 2
= 2(2T(n/4) + 2) + 2
= 4T(n/4) + 4 + 2
.
.
.
= 2k-1 T(2) + ∑(1≤i≤k-1) 2k
= 2k-1 + 2k – 2
= 3n/2 – 2 = O(n)
Kindly Note that 3n/2 – 2 is the best, average as well as the worst case number of comparison when n is a power of two.
2n – 2 comparisons for the Straight Forward method or technique, this is a 25% saving in comparisons. It can be illustrated that no calculation is under 3n/2 – 2 comparisons.
