I have been working with some colleagues on a metaheuristic for an NP-Hard optimization problem. It is a genetic algorithm using a steady-state population replacement strategy (at each iteration a single new chromosome is created and used to replace an older one). The algorithm iterates until it fails to find a solution which is better than the current incumbent optimum for a pre-set number of consecutive iterations. The algorithm has been tested on benchmark instances and proved empirically to be fast and effective, outperforming previous approaches.
We submitted our work to a journal and received rather favorable reviews. Among the modification requests, we were asked to state the time complexity of the procedure. While we have no difficulty to evaluate the (polynomial) complexity of a single iteration, we realized that, given the exponentially large solution space and our termination criterion, our algorithm could theoretically iterate an exponential number of times. Is this considered acceptable for a heuristic? After all, I was thinking, the same conclusion may even apply to a simple local search scheme, should it keep finding marginal improvements in its neighborhoods indefinitely without getting trapped in a local optimum.
Should we look into complexity analysis different from worst-case? Do you have references to works we may look into? Apologies if the question is too trivial, we are not "pure" computer scientists (although we submitted this work to a CS journal since we thought it was the right outlet for it).