An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum isa)Θ(nlogn)b)Θ(n)c)Θ(logn)d)Θ(1)Correct answer is option 'D'. Can you explain this answer?

Question

An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum isa)&Theta;(nlogn)b)&Theta;(n)c)&Theta;(logn)d)&Theta;(1)Correct answer is option 'D'. Can you explain this answer?

Answer

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.

Answer

To find an element in the list that is neither the maximum nor the minimum, we need to compare each element with the current maximum and minimum values.

First, we initialize two variables: max and min. We set max to the first element in the list and min to the second element in the list (assuming the list contains at least two elements).

Then, we iterate through the remaining elements in the list, starting from the third element. For each element, we compare it with the current max and min values.

If the element is greater than the current max value, we update max to be the element.

If the element is smaller than the current min value, we update min to be the element.

Finally, we return the number of comparisons we made to find an element that is neither the maximum nor the minimum.

The number of comparisons can be calculated as follows:

Number of comparisons = n - 2

Explanation: We have to compare each element (except the maximum and minimum) with the current max and min values. Since there are n elements in the list and we don't need to compare the maximum and minimum elements, we subtract 2 from the total number of elements to get the number of comparisons.

Therefore, the number of comparisons to find an element in this list that is neither the maximum nor the minimum is n - 2.

Similar Computer Science Engineering (CSE) Doubts

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

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2026 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company