This research suggests a new approach for stopping criterion of search techniques (for example, Genetic Algorithms (GA), Simulated Annealing (SA), Ant Colony (AC), Particle Swarm Optimization (PSO), etc.). The new stopping criterion statistically ensures that the initial improvement process (“warmup period”) reaches a plateau zone before applying a trade-off optimization of the stopping time. Preliminary results show that in comparison, most other contemporary stopping criteria, can either lead to premature termination (damaging solution’s quality), or lead to a significant waste of time (without any knowledge or awareness to these consequences). To implement the proposed approach, first, the length of a warmup period is identified, followed by a relatively flat duration of the objective function - to be approximated as a static distribution process. This approximation enables using record breaking statistics for stopping inference rules. In addition, a new bound on the optimal solution is proposed based on the Chebyshev inequality.