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:
- For $n$ distinct numbers, there are $n!$ possible orderings.
- There is only one correct sorted sequence of the $n$ numbers.
- 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.
- So $\log_2(n!)$ comparisons are required.
Then, the argument was generalized:
- Define a space of input possibilities
- Define the goal space, a subset of the input space
- Define the amount of information that is gained at each step of the computation
- 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:
- prove lower bounds,
- define an input space,
- define a goal space which is a subset of the input space, and
- do not rely on information arguments?