Number of comparisons to find second minimum element in an Array

Given an array of numbers, we need to find the second min element with optimal number of comparisons.

Let’s compare two elements (side by side) and get next set of min element list. Recursively, we end up with lowest number in the last iteration as mentioned below.

Finding Min Using Tournament Method

Now, how many comparisons we took to find least number here are:

n/2 + n/4 + n/8 + …. = a/(1-r) = n/2*1/(1-1/2) = n

So, it took n comparisons to find the least number. Now, to find the 2nd least number, can we reuse the previous states we used to find 1st least number ? If you observe the below figure, rectangle numbers will definitely contain the 2nd least number. And, identifying these numbers is easy, each recursive iteration we are comparing side by side numbers.

The reason why we went the tournament way (as opposed to serial comparison) is that we can leverage the reverse tree to find the second minimum value with log(n) comparisons (asymptotic), hence the solution represents marked improvements over 2n (ignoring constant) comparisons as required by trivial method.

Here is the logic to find second minimum value.

The logic is that at some point the minimum element (root element) must have knocked out the second minimum element. So, by backtracking from the root element (minimum) all the way to the top and checking all the adjacent elements to the root element (for each row) we can find the second minimum. The key point to note is that at any level (above root level), the adjacent elements can be obtained by the index of root element at this level. Therefore, you don’t need to scan complete sub-array (of recursion tree at any level). The adjacent elements for n-1 level is obtained as follows:

Adjacent Left (n-1 level) : 2 * (root index for nth level)
Adjacent Right(n-1 level): 2 * (root index for nth level) + 1

Therefore, for each row of the recursion tree, you just need to perform two comparisons to find the root element index to obtain the adjacent elements of row above. Refer to Figure 3 below. One of the elements marked in green box must be second minimum.

Finding 2nd Minimum using optimized back-tracking

So, how many comparisons we make using this method. Let’s calculate (ignoring constants): 

Comparisons for finding minimum: n
Comparisons for finding 2nd minimum: log(n)
Total: n + log(n)

Thus this method offers marked improvement over crude method.

Leave a Reply

Your email address will not be published. Required fields are marked *