Write down the algorithm for finding the minimum and maximum number from a number list using divide and conquer method.
Subject Algorithm Design
NU Year Set: 4.(a) Marks: 5 Year: 2008

  Algorithm for straight forward maximum and minimum

StraightMaxMin(a,n,max,min)

// set max to the maximum and min to the minimum of a[1:n].

{

     max := min := a[1];

     for i := 2 to n do

     {

           if(a[i] > max) then max := a[i];

           if(a[i] > min) then min := a[i];

     }

}

Analyzing the Straight Forward Method

                In analyzing the time complexity of this algorithm, we have to concentrate on the number of element comparisons. This algorithm requires 2(n-1) element comparisons in the best, average, and worst cases. An immediate improvement is possible by realizing that the comparison a[i] < min is necessary only when a[i]>max is false.

                Now the Best case occurs when the elements are in increasing order. The number of element comparisons is n-1. The worst case occurs when the element are in decreasing order. In this case number of comparisons is 2(n-1).

Login to post your comment.