Complexity

Question

An unordered list contains n distinct elements. Number of comparisons to find element larger than second minimum is

O(1)

O(n)

None

Comments

i think answer should be O(n)

because we have given a list so to find second minimum it will take O(n) then we will iterate again to find the larger element than this second minimum for that we just need to take two var first in which we see whether this given element is greater than second min and using other we will ensure that it should be least large

---

O(1) time.

Answer 1

the trick here.

since it is given that the list has distinct elements

=>when we select any 3 numbers the largest of the 3 will always be greater than the second minimum.

Number of comparisons to find element larger than second minimum

1. suppose there are numbers  2,3,8,1,4,5,9
2. take any 3 no. lets take 3,8,1.
3. select the greatest number from it  i.e. 8. we need only 2 comparisons (  O(1) )
4.  8 > 2.... answer.

Comments

If you solved this question- https://gateoverflow.in/8113/gate2015-2-22  then you can get the logic begind it...

Really good& tricky question..👍

---

It is not asking you to find second minimum element.

It is asking you to find any no. Greater than second minimum.

-----------------------------------------------------------------------------------------

Lets take a smaller problem for better understanding.

If i give you a list and tell you to find any no. Greater than minimum element of list.

Then you select 2 numbers  and after selecting those 2 numbers 2 cases can be possible

Case 1.  In that 2 numbers it is possible that you have included the minimum element. so you compare the two numbers and display the greater one. Hence , it will be greater than the minimum element.(Since you compared it with the minimum no. of the list )

Case 2. In that 2 numbers the minimum element of list is not included. So you can display any one of them as output (since both are greater than minimum element of list ) but for your surity you select the greater number and display it. (Since it is greater than some element of the list =>it is definitely greater than minimum element of the list ).

------------------------------------------------------------------------------------------

Same is the case for selecting for a number greater than 2nd minimum element of list. Just for surity we are comparing the three selected numbers.

(Since the greatest of the 3 numbers is greater than atleast 2 numbers => it will be definitely greater than the 2nd minimum element of the list )

---

@Satbir well explained..

Are you gate2020 aspirant?