edited by
17,426 views
61 votes
61 votes

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

  1. $\Theta(n \log n)$
  2. $\Theta(n)$
  3. $\Theta(\log n)$
  4. $\Theta(1)$
edited by

6 Answers

Best answer
120 votes
120 votes

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

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

edited by
19 votes
19 votes
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
3 votes
3 votes
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)
3 votes
3 votes
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
Answer:

Related questions

25 votes
25 votes
3 answers
1
go_editor asked Feb 12, 2015
6,931 views
Given below are some algorithms, and some algorithm design paradigms.$$\begin{array}{ll|ll}\hline \text{1.} & \text{Dijkstra's Shortest Path} & \text{i.} & \text{Divide a...