Progress of algorithms in problem spaces

Question

Continuing in the vein of two prior questions (1) and (2), we started with sorting, where we had

1. a set of $n!$ input possibilities
2. a goal space of only one element consisting of the one correct sorted sequence

We then arrived at a generalized argument which I'll alter slightly and call A:

1. Define a space of input possibilities
2. Define the goal space, a subset of the input space
3. Reason about constraints in order to set a lower bound

Three Questions: given that there are quadratic algorithms for sorting,

1. Can we conclude for the quadratic sorting algorithms, where we have an input space of $n!$ input possibilities and roughly $n^2$ steps, that there are $O(n!/n^2)$ possibilities removed from the search space per step on average?
2. Let's say we're given a problem formalizable in the form of argument A above where the input space is exponential in terms of the size of the input, $O(2^n)$, and the problem is solvable in polynomial time, $O(n^c)$, for some constant $c$. Can we conclude there are $O(2^n/n^c)$ possibilities removed from the search space per step on average?
3. Can we at least conclude that a $O(2^n)$ problem cannot be solved in polynomial time by removing one element from the input space per step?

Answer 1

1. Yes and No. If you see this as "amortized" number of possibilities removed in each step, then yes (follows trivially since you need $n^2$ time but have a search space of $n!$), but it is very difficult to formalize a notion of how many possibilities in each step are removed. You would need a notion of what a "step" is. An elementary operation, like an addition? Then how does one addition in the middle of, for instance, bubble sort reduce the search space? Instead, you have some kind of "checkpoints" during the algorithm at which the search space gets smaller, for instance when you find the 1st element, the 2nd, and so on. A concrete counter example to your idea is an algorithm that uses $n^2$ time in a dummy loop, and then solves the problem. In the first $n^2$ steps therefore, the solution space does not get smaller.

2. No, see above.

3. Yes, trivially?