|NU Year||Set: 4.(a) Marks: 5 Year: 2008|
Algorithm for straight forward maximum and minimum
// 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).