GATE CSE 2015 Set 2 | Question: 22

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 is

• A. $\Theta(n \log n)$
• B. $\Theta(n)$
• C. $\Theta(\log n)$
• D. $\Theta(1)$

Comments

simple
As elements are distinct so just take numbers which are neither minimum nor maximum can be done in $\Theta(1)$ time.

---

when professor wants to test our reading skills, grammar knowledge, and concentration

---

Take an array with three elements we can easily find the element that is neither maximum and nor minimum in Θ(1) time.

Answer 1

Correct Option: D – $\Theta(1)$

Because all elements are distinct, select any three numbers and output $2$nd largest from them.

Comments

• If in the same question 'distinct' keyword is not given, we will have to get 3 distinct elements and this would take O(n) time in the worst case. From these 3 distinct elements the middle element is neither minimum nor maximum. In this case it is O(n).
• If in the same question if we had to find the element that is not second minimum or second maximum, then we need to take any 5 elements and the median of these 5 elements will not be second minimum and also it will not be the second maximum. In this case it is O(1).

---

Very important observation :)

---

neither maximum nor minimum element : a is greater than at least 1 element & less than at least 1 element

neither second maximum nor second minimum : 

second maximum < exactly 1 element which is the maximum

second minimum > exactly 1 element which is the minimum

Thus, 

not second maximum : either max or < at least 2 elements

not second minimum : either min or > at least 2 elements  

not second maximum and not second minimum : < at least 2 elements and > at least 2 elements (no need to find min or max !)

therefore 5 elements will definitely work

a < b < c < d < e :      //return c 

Answer 2

they ask for an element which should not be minimum or maximum so We only need to consider any 3 elements and compare them. So the number of comparisons is constants, that makes time complexity as Θ(1)

Let us take an array {11, 20, 16, 7, 90}. Output can be 11 or 16 or 20 as

min = 7 and max = 90

Pick any three elements from given list. Let the three elements be 11, 20 and 7.

Using 3 comparisons, we can find that the middle element is 11.

meaning need to find middle element from 3 elements

Answer 3

Since all the elemets are distinct,taking any 3 elemets from array will guaratee that one element is smaller and one element is greater than this element.

Example : taking 3,2,1

here 2 is greater than 1 and smaller than 3.

This condition is true for any 3 elements of array. So choosing randomly 3 elements is sufficient to find an element which is neighter maximum nor minimum.

In worst cast out of choosen 3 elements one is maximum,one is minimum and 3rd is between them.So it is ensured in choosing only 3 elements.thus O(1)

Comments

I think it is O(n) but  thetha(1) is also ok let consider n=3,4,5,.....N

For n=3,4,5,.....And linear it is thetha(1)

While for very large it is O(n)  comparision

Answer 4

It is bit clear that it requires O(1)

But if in question they mention that the list contains repetition of elements

Like 1 1 1 1 1 1 .since we can't get the element which is not min and max but we need to compare hole list then we require O(n)

Plz correct me if my logic is wrong

Comments

Yes Correct  For It Distant it O(1)