4 - A selection problem

Summary

Introduction

Let X and Y be two finite disjoint sets of elements over some ordered type and of combined size greater than k. Consider the problem of computing the kth smallest element of X ⋃ Y. By definition, the kth smallest element of a set is one for which there are exactly k elements smaller than it, so the zeroth smallest is the smallest. How long does such a computation take?

The answer depends, of course, on how the sets X and Y are represented. If they are both given as sorted lists, then O(∣X∣+ ∣Y∣) steps are sufficient. The two lists can be merged in linear time and the kth smallest can be found at position k in the merged list in a further O(k) steps. In fact, the total time is O(k) steps, since only the first k + 1 elements of the merged list need be computed. But if the two sets are given as sorted arrays, then – as we show below – the time can further be reduced to O(log ∣X∣+log∣Y∣) steps. This bound depends on arrays having a constant-time access function. The same bound is attainable if both X and Y are represented by balanced binary search trees, despite the fact that two such trees cannot be merged in less than linear time.

The fast algorithm is another example of divide and conquer, and the proof that it works hinges on a particular relationship between merging and selection.