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.

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.