Write down the algorithm for finding the minimum and maximum number from a number list using divide and conquer method.
Subject Algorithm Design 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;

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). 