Java Reference
In-Depth Information
This recurrence (and the corresponding algorithm) yields T(n) = d3n=2e 2
comparisons. Is this optimal? We now introduce yet another tool to our collection
of lower bounds proof techniques: The state space proof.
We will model our algorithm by defining a state that the algorithm must be in at
any given instant. We can then define the start state, the end state, and the transitions
between states that any algorithm can support. From this, we will reason about the
minimum number of states that the algorithm must go through to get from the start
to the end, to reach a state space lower bound.
At any given instant, we can track the following four categories of elements:
• Untested: Elements that have not been tested.
• Winners: Elements that have won at least once, and never lost.
• Losers: Elements that have lost at least once, and never won.
• Middle: Elements that have both won and lost at least once.
We define the current state to be a vector of four values, (U;W;L;M) for
untested, winners, losers, and middles, respectively. For a set of n elements, the
initial state of the algorithm is (n; 0; 0; 0) and the end state is (0; 1; 1;n2). Thus,
every run for any algorithm must go from state (n; 0; 0; 0) to state (0; 1; 1;n 2).
We also observe that once an element is identified to be a middle, it can then be
ignored because it can neither be the minimum nor the maximum.
Given that there are four types of elements, there are 10 types of comparison.
Comparing with a middle cannot be more efficient than other comparisons, so we
should ignore those, leaving six comparisons of interest. We can enumerate the
effects of each comparison type as follows. If we are in state (i;j;k;l) and we have
a comparison, then the state changes are as follows.
U : U (i 2; j + 1; k + 1; l)
W : W (i;
j 1; k;
l + 1)
L : L
(i;
j;
k 1; l + 1)
L : U
(i 1; j + 1; k;
l)
or
(i 1; j;
k;
l + 1)
W : U (i 1; j;
k + 1; l)
or
(i 1; j;
k;
l + 1)
W : L (i;
j;
k;
l)
or
(i;
j 1; k 1; l + 2)
Now, let us consider what an adversary will do for the various comparisons.
The adversary will make sure that each comparison does the least possible amount
of work in taking the algorithm toward the goal state. For example, comparing a
winner to a loser is of no value because the worst case result is always to learn
nothing new (the winner remains a winner and the loser remains a loser). Thus,
only the following five transitions are of interest:
