Tim, when I said relative to a space I did not mean relative to its size.

Sure - you aren't making the same mistake as the original poster in that department.

Comparing to the size of the search space is pretty daft - since the search space is often unbounded in optimisation problems.