⌋ comparisons is performed; if n is even, we perform 1
more initial comparison out of the first 2 elements, and thus for a total of
3 ⋅
comparisons. In either case, 3 ⋅⌊
⌋ of comparisons is performed.
Knowledge Base > Algorithm > Selection Algorithm
Overview
A simple linear search to find a minimum or a minimum independently from a list takes at most O(n - 1) comparisons, and runs at O(n) time. However, there is another way to reduce the number of comparisons by finding both the maximum and minimum in pair of n elements. This approach still runs at linear time, O(n).
Algorithm
The strategy is to first pair the first 2 elements to determine the initial value of maximum and minimum, if n is even; or set both maximum and minimum to value of the first element, if n is odd. Then, we compare the rest of elements by pairs, smaller to the minimum and larger to the maximum. That is,
Analysis
Therefore, this approach guarantee us 3 comparisons is taken for each 2 elements.
If n is odd, then 3 ⋅⌊⌋ comparisons is performed; if n is even, we perform 1
more initial comparison out of the first 2 elements, and thus for a total of
3 ⋅ comparisons. In either case, 3 ⋅⌊⌋ of comparisons is performed.