5
$\begingroup$

I am having trouble with the following homework assignment:

Give an algorithm that finds the second smallest of n elements in at most $n + \lceil\log(n)\rceil - 2$ comparisons.

I have been trying to find an algorithm myself, and believe I have to check the elements in pairs and then recurse on the smallest elements. However, when I tried an algorithm like this the amount of comparisons it took where $n + \lceil\log(n)\rceil$ (according to me).

This is the algorithm in question:

1. secondSmallest(A[n]) 2.    if A.length >= 2 then 3.       for i = 1 to i = A.length do 4.          if A[i] < A[i + 1] then 5.             B[(i+1)/2] = A[i] 6.             i + + 7.          else 8.             B[(i+1)/2] = A[i + 1] 9.            i + + 10.         endif 11.      return secondSmallest(B[n]) 12.    else 13.       if A[1] < A[2] then 14.          return A[2] 16.       else return A[1] 17.       endif 18.    endif 

Note: this is pseudocode, and by no means accurate. And the logarithm is a BASE 2 logarithm.

  • 1
    Is that supposed to be a natural logarithm? Or base 2 perhaps?2012-03-04
  • 0
    What about binary searching for the smallest element using lg(n) comparisons, removing the smallest element from the array, and then do another binary search on the array using lg(n) comparisons and returning the smallest element. That would be lg(n) + lg(n) comparisons.2012-03-04
  • 1
    Oh, I am indeed very sorry. It is supposed to be a base 2.2012-03-04
  • 1
    @SuprDewd Yes, I found that myself to. But we are meant to find one that takes n+lg(n)-2. Mainly because that would in fact be faster then your solution (since we would have to move all elements when doing that)2012-03-04
  • 2
    @SuprDewd That requires the array to be sorted. It can be done in $n + \lg(n) - 2$ comparisons for any input array.2012-03-04
  • 0
    I know the theory behind it, I'm just not sure how I'd attempt to do it. You know why it takes a minimum of n-1 comparisons to find the smallest element, right? Well, without giving it away, once you know the smallest, how would you develop a short list of candidates for the runner up?2012-03-04
  • 0
    I believe I have a good idea now. First, we get the smallest element. And remove this one. Then we take a random element from the array, and compare this to all the other elements, remembering the smallest one. In the end we will have then taken n+log(n)-2 comparisons if I am correct.2012-03-04
  • 0
    Your proposed algorithm doesn't work -- imagine the case where the input is already sorted. Then the first thing that happens in your code is that the true second-smallest element is discarded and never considered again.2012-03-04

2 Answers 2

12

SKETCH: Assuming that you’re allowed to use extra storage, run the comparison as a single elimination tournament, keeping a record of the entries beaten by each winner along the way. (Low number wins.) When you get an overall winner, you have only to identify the winner among the $\lceil \lg n\rceil$ contestants beaten by the overall winner.

Added: On further thought, I see that one doesn’t actually need additional memory, if one rearranges the list. Implement the single elimination tournament as follows.

Suppose that the numbers are $a_0,a_1,\dots,a_{n-1}$. On the first pass compare $a_{2k}$ with $a_{2k+1}$ for $0\le k<(n-1)/2$; if $a_{2k}>a_{2k+1}$, interchange them. On the second pass compare $a_{4k}$ with $a_{4k+2}$ for $0\le k<(n-2)/4$; if $a_{4k}>a_{4k+2}$, interchange the pair $\langle a_{4k},a_{4k+1}\rangle$ with the pair $\langle a_{4k+2},a_{4k+3}\rangle$. On the $i$-th pass compare $a_{2^ik}$ with $a_{2^ik+2^{i-1}}$ for $0\le i<(n-2^{i-1})/2^i$; if $a_{2^ik}>a_{2^ik+2^{i-1}}$, interchange the blocks of length $2^{i-1}$ beginning at $a_{2^ik}$ and $a_{2^ik+2^{i-1}}$. This continues as long as $n-2^{i-1}>0$, i.e., until $n\le 2^{i-1}$; thus, if the last pass is the $m$-th pass, then $2^{m-1}

The numbers that are now $a_{2^i}$ for $i=0,\dots,m-1$ are the numbers that lost to $a_0$ in direct comparisons; every number in the set that is neither $a_0$ nor one of these $m$ numbers lost a direct comparison to one of these $m$ numbers and therefore cannot be the second-smallest number in the set. Thus, the second-smallest number is the smallest of the $a_{2^i}$ for $i=0,\dots,m-1$. There are $m$ of these numbers, so it takes $m-1$ comparisons to find the smallest.

Altogether, then, this algorithm takes $$(n-1)+(m-1)=n-1+\lceil\lg n\rceil-1=n+\lceil\lg n\rceil-2$$ comparisons, as required.

  • 0
    You mean $\lceil \log n\rceil$, correct?2012-03-04
  • 0
    @Mike: I sure do; thanks. Fixed.2012-03-04
  • 0
    So, you first get the smallest element in the array, taking n comparisons. And then you use a divide and conquer algorithm to find the smallest one out of the remaining elements (which would then take log(n) comparisons, however since you lack one element it would take log(n)-2 comparisons)?2012-03-04
  • 1
    @Ruddie: No, that’s not at all what I described. The first pass takes $n-1$ comparisons, arranged in a binary tree; the second pass involves only $\lceil\lg n\rceil$ numbers and does $\lceil\lg n\rceil-1$ comparisons.2012-03-04
  • 0
    In the list of entries beaten by each winner the second smallest element is either first or second so finding it needs only one comparison.2012-03-04
  • 0
    In the kth round in the tournament there are {n/2^k} comparisons where {x} is the smallest integer larger than x. This is upper bounded by n/2^k+1 and summing over k gives something like n-2+logn. To me the value in the question is getting the constant on the n term to be 1, the other terms quickly become irrelevant.2012-03-04
  • 0
    @David: You need only the list of entries beaten by the winner of the single-elim. tournament, and there’s no predicting which of those is the second-placer.2012-03-05
  • 0
    As Timofei shows, I don't think the second highest is in one of the places you say. The first number beaten by the highest is left in an odd numbered position, which could be any odd number, and never moves after that.2012-06-27
  • 0
    If all we are interested in is bounding the number of comparisons, we can keep track of the original index of the elements of the list for free. From the original index of the final $a_0$ you can quite easily compute the final resting place of those numbers which lost to it.2012-06-27
  • 0
    @Ross: He’s right: I slipped up on the swapping, which must be of blocks of entries rather than just the two being compared. In other words, I’m swapping subtrees, not elements. I think that it’s fixed now.2012-06-28
1

Consider the following list of numbers: $3, 4, 5, 2, 1, 7, 8, 9$.

While passing through the first stage of Brian M. Scott's algorithm above, after each pass the list changes as follows: $$ \begin{array}{l|cccccccc} & a_0 & a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & a_7 \\ \hline \text{start} & 3 & 4 & 5 & 2 & 1 & 7 & 8 & 9 \\ \text{pass 1} & 3 & 4 & 2 & 5 & 1 & \color{blue}{7} & 8 & 9 \\ \text{pass 2} & 2 & 4 & 3 & 5 & 1 & \color{blue}{7} & \color{blue}{8} & 9 \\ \text{pass 3} & 1 & 4 & 3 & 5 & \color{blue}{2} & \color{blue}{7} & \color{blue}{8} & 9 \end{array} $$

(The numbers in blue are those that have been compared to the final $a_0$ (that is, $1$) up to (and including) that pass through the algorithm.)

Brian M. Scott then states

The numbers that are now $a_{2^i}$ for $i=0,\ldots,m−1$ are the numbers that lost to $a_0$ in direct comparisons;...

However neither $4$ nor $3$ were ever compared directly to $1$, and the indicies of $7$ and $8$ are not of that form.

Have I missed something?

  • 0
    No, you’ve not missed something; I didn’t state the algorithm quite right. At each stage you have to interchange *blocks* rather than just the two numbers being compared. I’ve revised the answer accordingly.2012-06-28