Generalizing the Comparison Sorting Lower Bound Proof

Question

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.

Answer 1

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:

• Lower-bounds, Part 2/4: Information Theory

The first part is here:

• Lower-bounds, Part 1/4: Introduction, Decision Trees