Made easy workbook

Question

We've been given an unordered list having n distinct elements,the no. Of comparison to find an element that is neither the 2nd minimum nor the 2nd maximum is?

Answer 1

To find an element that is neither the 2nd minimum nor the 2nd maximum, We can pick any five elements from the array and sort them...the middle element of these five elements will be guaranteed to be a number which is neither the 2nd minimum nor the 2nd maximum,

Hence, let's pick the first five elements of the array and apply Insertion sort on them. We will, in worst case, have to make $10$ comparisons. And time complexity of this algorithm will be $O(1)$.

Comments

What if we try not to choose any 5elements ,instead we form a heap and comparing?