Hmm few comparsion

Computer Science Level 3

Given an unordered list of $n\geq 3$ distinct elements, what is the minimum number of comparisons required to find an element that is neither maximum nor minimum?

O(n\log(n))

O(n)

O(\log(n))

O(1)

2 solutions

Ivan Koswara
Oct 12, 2015

Assume $n \ge 3$ , so such element exists. Sort the first three elements and pick the middle element. This cannot be the minimum (otherwise it would be sorted as first position) nor the maximum (otherwise it's the third position). The number of comparisons is simply $3 = O(1)$ ; we don't need to look at the rest of the input.

Yeah, but if N>3, there is no middle element Take 4, if you weigh any two, they could be minimum and maximum, but you have no way of knowing unless you weigh again The solution should be 2

Alex Li - 5 years, 8 months ago

If N>3, you would still only select the first three elements. Since all elements are distinct, any triplet must contain a small, middle, and large value. By choosing the middle value, you are guaranteed it is neither the maximum nor minimum of the entire list. (The question asks only for an element which is in-between the list's min and max. )

Dan Wilhelm - 5 years, 8 months ago

Darryl Dennis
Oct 12, 2015

O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set. (https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation)

As Ivan has pointed out

In this problem any three elements of the list can be selected randomly and then sorted to find an element to satisfy the requirements for the answer. The algorithm would always be required to do only three comparisons regardless of the size of the list, therefore 0(1) is the correct answer

In other words the size of this list will not change the time required to find a element that satisfies the requirements. /

Hmm few comparsion

2 solutions

0 pending reports