Menu
For an array of size N, what is the number of comparisons required?
317
We can do it in O(n) or "linear time" meaning as the array gets bigger the number of comparisons grows at the same rate. Loop through the array tracking the max, that's the usual way to find the max. When you find a new max, the old max becomes the 2nd highest number.
The formula for the minimum number of comparisons to find the minimum and the maximum elements is ( 3n / 2 ) – 2 where n is the size of the array.
The optimal algorithm uses n+log n-2 comparisons. Think of elements as competitors, and a tournament is going to rank them.
First, compare the elements, as in the tree
| / \ | | / \ / \ x x x x this takes n-1 comparisons and each element is involved in comparison at most log n times. You will find the largest element as the winner.
The second largest element must have lost a match to the winner (he can't lose a match to a different element), so he's one of the log n elements the winner has played against. You can find which of them using log n - 1 comparisons.
The optimality is proved via adversary argument. See https://math.stackexchange.com/questions/1601 or http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdf or http://www.imada.sdu.dk/~jbj/DM19/lb06.pdf or https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf
167
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
