An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is


An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is
A
Θ(nlogn)
B
Θ(n)
C
Θ(logn)
 D
Θ(1)

Explanation:

We only need to consider any 3 elements and compare them. So the number of comparisons is constants, that makes time complexity as Θ(1) The catch here is, we need to return any element that is neither maximum not minimum. Let us take an array {10, 20, 15, 7, 90}. Output can be 10 or 15 or 20 Pick any three elements from given liar. Let the three elements be 10, 20 and 7. Using 3 comparisons, we can find that the middle element is 10.

Leave a comment

Your email address will not be published. Required fields are marked *