## The comparison oracle for linear orders

We are going to consider a linearly ordered set; we will assume that this set can be accessed only through an oracle that, given any pair u,v of distinct keys, announces that
• u precedes v, or that
• v precedes u.

## Example 1: Merging sorted sequences

We propose to show that

merging a sorted sequence of n keys with another sorted sequence of n keys
takes at least 2n-1 calls of the comparison oracle in the worst case.

For this purpose, consider an arbitrary algorithm A that merges sequences u1, u2, ...., un and v1, v2, ...., vn such that

u1 < u2 < ....< un and v1 < v2 < ....< vn.
and that accesses the input only through the comparison oracle. Let us simulate the oracle by the following algorithm:
```repeat ui and vj = the next pair of keys to be compared;
if   i=j
else if   i<j
end
end
end
```
Another way of describing this algorithm is saying
• answer all questions as if u1 < v1 < u2 < v2 < ....< un < vn.
If A calls the oracle fewer than 2n-1 times, then at least one of the 2n-1 pairs
(u1 and v1), (v1 and u2), (u2 and v2), ... , (vn-1 and un), (un and vn)
of keys that are adjacent in the input template remains uncompared, and so the answers provided by the oracle match not only this template, but also the template where the order of these two keys is switched.

For example, let us take n=5. If u2 and v2 remain uncompared, then the answers provided by the oracle match both templates

u1 < v1 < u2 < v2 < u3 < v3 < u4 < v4 < u5 < v5
and
u1 < v1 < v2 < u2 < u3 < v3 < u4 < v4 < u5 < v5.
If v3 and u4 remain uncompared, then the answers provided by the oracle match both templates
u1 < v1 < u2 < v2 < u3 < v3 < u4 < v4 < u5 < v5
and
u1 < v1 < u2 < v2 < u3 < u4 < v3 < v4 < u5 < v5.
And so on.

## Example 2: Finding the maximum

We propose to show that

finding the maximum of n keys takes at least n-1 calls of the comparison oracle in the worst case.

For this purpose, consider an arbitrary algorithm A that finds the largest of keys u1, u2, ...., un and accesses the input only through the comparison oracle. Let us simulate the oracle by the following algorithm:

```for i = 1 to n do  candidate(ui)=YES end
repeat ui and uj = the next pair of keys to be compared;
if   i<j
candidate(ui)=NO;
candidate(uj)=NO;
end
end
```
Another way of describing this oracle is saying
• answer all questions as if u1 < u2 < ... < un
(and remove a key from the list of candidates for the maximum
as soon as it has been pronounced smaller than another key).
If A calls the oracle fewer than n-1 times, then at least two of the n keys uk have candidate(uk)=YES; one of these is un and the other has k<n. But then the answers provided by the oracle match not only the initial template, but also the template
u1 < u2 < ... < uk-1 < uk+1 < ... < un < uk.

The two oracle simulations used in Examples 1 and 2 have a common feature: they start out with an input template,
u1 < v1 < u2 < v2 < ... < un < vn in Example 1
and
u1 < u2 < ... < un in Example 2,
and answer all questions as if the unknown input matched this template. Such oracle simulations might be called non-adaptive. More sophisticated oracle simulations construct the template incrementally in a way that depends on A's questions. One example of such an adaptive oracle simulation is coming up next.

## Example 3: Finding the median

We propose to show that

finding the median of 2k+1 keys
takes at least 3k calls of the comparison oracle in the worst case.

For this purpose, consider an arbitrary algorithm A that finds the median of a set S of 2k+1 keys and accesses the input only through the comparison oracle. Let us simulate the oracle by the following algorithm:

```/* Initialization */
for all elements u of S
do  rank(u) = "unassigned";
candidate(u) = YES;
end

num_small = 0, num_large = 0;
while num_small < k and num_large < k
do    u,v = the next pair of keys to be compared;
if   rank(u) = "unassigned"
then if   rank(v) = "unassigned"
then num_small = num_small+1, rank(u) = num_small;
num_large = num_large+1, rank(v) = k+1+num_large;
else if   rank(v) < k+1
then num_large = num_large+1, rank(u) = k+1+num_large;
else num_small = num_small+1, rank(u) = num_small;
end
end
else if   rank(v) = "unassigned"
then if   rank(u) < k+1
then num_large = num_large+1, rank(v) = k+1+num_large;
else num_small = num_small+1, rank(v) = num_small;
end
end
end
if   rank(u) < rank(v)
if k+1 < rank(u) then candidate(v) = NO end
if rank(v) < k+1 then candidate(u) = NO end
if k+1 < rank(v) then candidate(u) = NO end
if rank(u) < k+1 then candidate(v) = NO end
end
end

/* Completing the template */
w = an element of S such that rank(w) = "unassigned";
rank(w) = k+1;
if   num_small = k
then for all elements u of S
do  if   rank(u) = "unassigned"
then num_large = num_large+1, rank(u) = k+1+num_large;
end
end
else for all elements u of S
do  if   rank(u) = "unassigned"
then num_small = num_small+1, rank(u) = num_small;
end
end
end

repeat u,v = the next pair of keys to be compared;
if   rank(u) < rank(v)
if rank(u) is at least k+1 then candidate(v) = NO end
if rank(v) is at most  k+1 then candidate(u) = NO end
if rank(v) is at least k+1 then candidate(u) = NO end
if rank(u) is at most  k+1 then candidate(v) = NO end
end
end
```
Let us say that a call of oracle is useful if it brings about setting ` candidate(w)=NO ` for some `w`. In the adaptive stage, at least k calls of the oracle are countered by setting the value of rank(u) or rank(v) or both in such a way that
the smaller of rank(u), rank(v) is smaller than k+1 and
the larger   of rank(u), rank(v) is larger   than k+1;
none of these calls are useful. It follows that, as long as A calls the oracle fewer than 3k times, at most 2k-1 of these calls are useful, and so in the end at least two distinct elements `w` of S have ` candidate(w)=YES`. In particular, there is an element `x` of S such that ``` rank(x)``` is not ` k+1` and such that ``` candidate(x)=YES```. If rank(x) < k+1, then set
```    newrank(x) = k+1,
newrank(y) = rank(y)-1  whenever rank(x) < rank(y) < k+2,
newrank(y) = rank(y)    for all other choices of y;
```
if rank(x) > k+1, then set
```    newrank(x) = k+1,
newrank(y) = rank(y)+1  whenever k < rank(y) < rank(x),
newrank(y) = rank(y)    for all other choices of y;
```
The answers that oracle has provided are consistent with the linear order defined by rank(.) as well as with the linear order defined by newrank(.). However, the median with respect to rank(.) differs from x, which is the median with respect to newrank(.).

## Example 4: Finding a counterfeit coin

We have a number of coins which look alike; one of them is counterfeit and all of the remaining ones are genuine; all the genuine coins have an equal weight and the counterfeit coin is lighter. To find the counterfeit coin, we may use pharmacy scales as many times as necessary. In each weighing, we put an equal number of coins in each tray of the scales: the counterfeit is in the lighter set of coins or, in case the two sets are equally heavy, in the set of coins that has been left out.

We propose to show that

finding the counterfeit among n coins takes at least lg n / lg 3 weighings in the worst case.

For this purpose, consider an arbitrary algorithm A that finds the counterfeit in a set P of n coins and accesses the input only through the use of pharmacy scales. Let us simulate the outcomes of the weighings by the following algorithm:

```repeat L,R = the two sets of coins to be placed on the two trays;
/* we have |L|=|R| */
if   |L| > |P|/3
then answer "L is lighter than R";
P = L;
else answer "L and R are of equal weight";
remove both L and R from P;
end
/* the counterfeit is in P */
end
```
After t iterations, the size of P is at least n / 3t . In particular, if t < lg n / lg 3, then the size of P is greater than 1, and so the answers that the oracle has provided are consistent with at least two distinct choices of the counterfeit.

## Example 5: Sorting

We propose to show that

sorting n keys takes at least lg(n!) calls of the comparison oracle in the worst case.

For this purpose, consider an arbitrary algorithm A that sorts a set S of n keys and accesses the input only through the comparison oracle. Let us simulate the oracle by the following algorithm:

```P = the set of all linear orders on S;
repeat u,v = the next pair of keys to be compared;
P(u) = the set of all linear orders in P where u precedes v;
P(v) = the set of all linear orders in P where v precedes u;
if   |P(u|) > |P(v)|
P = P(u);
P = P(v);
end
end
```
After t iterations, the size of P is at least n! / 2t . In particular, if t < lg(n!), then the size of P is greater than 1, and so the answers that the oracle has provided are consistent with at least two distinct linear orders on S.

## A unified general setting and information-theoretic bounds

1. We start out with a set P of inputs.
• In Example 1, elements of P are all linear orders < on the set {u1, u2, ...., un, v1, v2, ...., vn} that satisfy
u1 < u2 < ....< un and v1 < v2 < ....< vn.
• In Example 2, elements of P are all linear orders < on the set {u1, u2, ...., un}.
• In Example 3, elements of P are all linear orders < on the set S of 2k+1 elements.
• In Example 4, elements of P are all the n coins suspected of being counterfeit.
• In Example 5, elements of P are all linear orders < on the set S of n elements.

2. The inputs in P can be accessed only indirectly, by means of an oracle.
• In Examples 1, 2, 3, 5, the oracle is the comparison oracle.
• In Example 4, the oracle is represented by the scales.
In general, the oracle is specified by a set Q of questions and each question is a function f defined on P. Each access of an input x by the oracle amounts to choosing a question f in Q and asking the oracle for the answer f(x).
• The comparison oracle is specified by questions fuv, one for each pair u,v of distinct elements of the linearly ordered set: fuv(<) is "u precedes v" whenever u < v and it is "v precedes u" whenever v < u.
• The oracle of Example 4 is specified by questions fLR, one for each pair L,R of disjoint and equally sized subsets of P; fLR(x) is "L is lighter than R" whenever x is in L, it is "R is lighter than L" whenever x is in R, and it is "L and R are of equal weight" whenever x is in neither L nor R.

3. With each input in P, we associate a single output.
• In Example 1, the output associated with < is < itself.
• In Example 2, the output associated with < is the largest (with respect to <) element of {u1, u2, ...., un}.
• In Example 3, the output associated with < is the median (with respect to <) element of S.
• In Example 4, the output associated with x is x itself.
• In Example 5, the output associated with < is < itself.
In general, let g denote the function that associates an output g(x) with each input x.

If A is an algorithm that attempts to determine g(x) of an unknown input x by calling the oracle as few times as possible, then an adversary strategy against A simulates the oracle in a way that attempts to keep g(x) unknown as long as possible. The non-adaptive adversary strategies are particularly simple: they have the form

```choose an element y of P;
repeat f = the next function in Q for which
the oracle is asked to return f(x);
end
```

The adaptive adversary strategies used in Examples 4 and 5 generalize as follows:

```repeat f = the next function in Q for which
the oracle is asked to return f(x);
w = an element of f(P) that
maximizes |{g(x) : x is in P and f(x)=w}|;
P = {x : x is in P and f(x)=w};
end
```
To analyze this algorithm, let us write
N = |g(P)| and k = max {|f(P)| : f is in Q} ;
In each iteration, let us enumerate the elements of f(P) as w1, w2, ...., wd and, for each of these elements wi, let us write
Pi = {x : x is in P and f(x)=wi}.
In this notation, w is a wj that maximizes |g(Pj)|; since the union of g(P1), g(P2), ...., g(Pd) is g(P), it follows that |g(Pj)| is at least |g(P)| / d, which is at least |g(P)| / k. Since this iteration replaces the current P by Pj, straightforward induction on t shows that
after t iterations, the size of g(P) is at least N / kt .
In particular, if t < lg N / lg k , then the size of g(P) is greater than 1, and so the answers that the oracle has provided are consistent with at least two distinct outputs. To put it differently,
determining the output takes at least lg N / lg k calls of the oracle in the worst case.
This lower bound, lg N / lg k, on the worst-case number of calls of the oracle, is known as an information-theoretic bound or a decision-tree bound.