1
$\begingroup$

For a college assignment we are supposed to prove that a lowerbound of $\lceil{n/2}\rceil$ comparisons holds for a selection algorithm that finds the smallest and second smallest element in an unsorted array with $n$ distinct elements.

My first intuition was to use a proof by contradiction assuming that an alogrithm exists that solves the problem with at most $\lceil{n/2}\rceil -1$ comparisons and proving that this is not possible.

A lot of proofs on the internet proof this lowerbound by assuming the algorithm uses a "tennis tournament" structure, first comparing the $n$ elements in pairs, and then comparing the $n/2$ "winners"in pairs, and so on to find the minimum Subsequently, doing the same for the $n-1$ elements which are not the minimum to find the 2nd smallest element.

However, for this assignment we are not allowed to make any assumptions about how the algorithm works, so the above proof will not be valid. I have tried to construct a proof by only making conclusions about the maximum height of the decision tree and its leaves but I keep hitting walls.

Is there a way to proof this lowerbound without making assumptions on how the algorithm works?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

If we do fewer than $\lceil n/2\rceil$ comparisons, then there are elements that haven't been compared to other elements at all. So we clearly cannot find the smallest element with any such algorithm.

$\endgroup$

You must log in to answer this question.