Let's start with the comparison sorting lower bound proof, which I'll summarize as follows:

  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.

Now consider the following generalization of the argument above:

  1. Define a space of possibilities and its size (in the case of sorting, $n!$ orderings)
  2. Define the goal state and its size (in this case, only one correctly sorted answer)
  3. Define the amount of information that is gained at each step of the computation (in this case, one bit since there are only two possible outcomes per comparison)
  4. Calculate the information difference between the space of possibilities (step 1) and the goal space (step 2) and divide by the information gain per step (step 3) to yield the lower bound on the number of steps (in this case, $(\log_2(n!)$ - $\log_2(1))$ / 1 = $\log_2(n!)$).

Please answer all the following questions. I'm less concerned with the correctness of the particulars of step 4 than I am with the correctness of steps 1 - 3.

  1. Are there any problems with the generalized argument?
  2. If the problems can be fixed, what are the fixes?
  3. If the problems can't be fixed, please point out the fatal ones and provide directions to sources which describe these lower-bounds proofs and their pitfalls.
  • 4
    $\begingroup$ The argument looks fine to me. $\endgroup$ – Yuval Filmus Nov 9 '12 at 3:45

The decision tree method for proving lower-bounds (like the $\Omega(n \lg n)$ lower-bound for comparison based sorting you mentioned) are often called information theory methods.

Here is a short video by Faith Ellen about this method:

The first part is here:


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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