To find the minimum value into an array of items, take the first item and to compare its value against the values of all other elements. Once we find a smaller element we continue the comparisons with its value. Finally we find the minimum.
We pass through the array with n steps and we need exactly n-1 comparisons.
Finding the maximum is identical to finding the minimum and requires n-1 comparisons!
Since they both are O(n) and need n-1 comparisons it’s natural to think that combining the two tasks will be O(n) and 2n – 2 comparisons. However we can reduce the number of comparisons!
Instead of taking only one item from the array and comparing it against the minimum and maximum we can take a pair of items at each step. Thus we can first compare them and then compare the smaller value with the currently smallest value and…
View original post 62 more words