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