UPPCL AE 2018:55

Question

An unordered list contains $n$ distinct elements. The number of comparisons to find an element in the list that is larger than the second minimum in the list is

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

Answer 1

I think just 3 comparisons are needed among 1st, 3 elements of the array. the elements greater in this 1st, 3 elements will definitely be greater than the 2nd minimum element.

Hence T(n)  = O(1)

Comments

but how we will find 2nd minimum of list?

---

It’s telling that just largest of 2^nd minimum means any number greater than 2^nd minimum you chose any three number to compare them and find largest number in 2 comparsions because list order or unordered.

ex unorder list = 4,5,6,2,1,3

           let we pick randomly 3 no of list     4,5,6  comparisons finding largest of 2^nd is 2 and number is 6