Progress of algorithms in problem spaces
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.
No, see above.
Yes, trivially?