There's a big field associated with optimisation. They use metrics like number of trials, time taken, resources used and the quality of the solution to measure the relative worth of optimisation processes. The size of the target relative to the size of the search space typically isn't used - because the search space is often unbounded, and the size of the target is usually pretty irrelevant. Of course, all this has been explained before.