Java Reference
In-Depth Information
We now go back to trying to improve the lower bounds proof. To do this,
we introduce the concept of an adversary. The adversary's job is to make an
algorithm's cost as high as possible. Imagine that the adversary keeps a list of all
possible inputs. We view the algorithm as asking the adversary for information
about the algorithm's input. The adversary may never lie, in that its answer must
be consistent with the previous answers. But it is permitted to “rearrange” the input
as it sees fit in order to drive the total cost for the algorithm as high as possible. In
particular, when the algorithm asks a question, the adversary must answer in a way
that is consistent with at least one remaining input. The adversary then crosses out
all remaining inputs inconsistent with that answer. Keep in mind that there is not
really an entity within the computer program that is the adversary, and we don't
actually modify the program. The adversary operates merely as an analysis device,
to help us reason about the program.
As an example of the adversary concept, consider the standard game of Hang-
man. Player A picks a word and tells player B how many letters the word has.
Player B guesses various letters. If B guesses a letter in the word, then A will in-
dicate which position(s) in the word have the letter. Player B is permitted to make
only so many guesses of letters not in the word before losing.
In the Hangman game example, the adversary is imagined to hold a dictionary
of words of some selected length. Each time the player guesses a letter, the ad-
versary consults the dictionary and decides if more words will be eliminated by
accepting the letter (and indicating which positions it holds) or saying that its not
in the word. The adversary can make any decision it chooses, so long as at least
one word in the dictionary is consistent with all of the decisions. In this way, the
adversary can hope to make the player guess as many letters as possible.
Before explaining how the adversary plays a role in our lower bounds proof,
first observe that at least n1 values must lose at least once. This requires at least
n 1 compares. In addition, at least k 1 values must lose to the second largest
value. That is, k direct losers to the winner must be compared. There must be at
least n + k 2 comparisons. The question is: How low can we make k?
Call the strength of element A[i] the number of elements that A[i] is (known
to be) bigger than. If A[i] has strength a, and A[j] has strength b, then the winner
has strength a + b + 1. The algorithm gets to know the (current) strengths for each
element, and it gets to pick which two elements are compared next. The adversary
gets to decide who wins any given comparison. What strategy by the adversary
would cause the algorithm to learn the least from any given comparison? It should
minimize the rate at which any element improves it strength. It can do this by
making the element with the greater strength win at every comparison. This is a
“fair” use of an adversary in that it represents the results of providing a worst-case
input for that given algorithm.
