Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the argument made in this question based on the comparison sorting lower-bounds proof, which runs as follows.

First, the comparison sorting lower-bounds proof was recited:

  1. For $n$ distinct numbers, there are $n!$ possible orderings.
  2. There is only one correct sorted sequence of the $n$ numbers.
  3. We are given that comparison ($<$) is the only operation we have that can narrow down the $n!$ possible orderings, and each comparison has only two possible outcomes.
  4. So $\log_2(n!)$ comparisons are required.

Then, the argument was generalized:

  1. Define a space of input possibilities
  2. Define the goal space, a subset of the input space
  3. Define the amount of information that is gained at each step of the computation
  4. Calculate the information difference between the space of possibilities and the goal space and divide by the information gain per step to yield the lower bound on the number of steps.

Both arguments above rely on information arguments to prove a lower bound on the number of steps.

Question: are there proofs and/or proof strategies like the above which:

  1. prove lower bounds,
  2. define an input space,
  3. define a goal space which is a subset of the input space, and
  4. do not rely on information arguments?
share|cite|improve this question
up vote 3 down vote accepted

The more general argument is an example of an adversary argument. A nice example is a lower bound for the number of comparisons needed to find the minimum and the maximum at the same time. Said number is $\lceil 1.5 n \rceil - 2$. You can try to construct the algorithm and prove its optimality, or just have a look at the paper.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.