Many current recognition systems use constrained search to locate objects in cluttered environments. Earlier analysis of one class of methods has shown that the expected amount of search is quadratic in the number of model and date features, if all the data is known to come from a single object, but is exponential when spurious data is included. To overcome this, many methods terminate search once an interpretation that is'good enough' is found. This paper formally examines the combinations of this approach, showing that choosing correct termination procedures can dramatically reduce the search. In particular, conditions are provided for the object model and the scene clutter such that the expected search is polynomial. The analytic results are shown to be in agreement with empirical data for cluttered object recognition.