Question

Let A[1..n] be an array of numbers. To find the largest number in A, one way is to divide A into two halves, recursively find the largest number in each half, and pick the maximum between the two.(a) Write a recursive algorithm to implement the above scheme. Write a recurrence relation describing the running time of the algorithm and solve it to give a tight bound on the running time of this algorithm.(b) Does this recursive algorithm perform better than an incremental algorithm that computes the largest element in A by iterating through the elements of A? Explain.

Answer 1

Check the explanation

Step-by-step 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]+"\\Min : "+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.