Suppose that we have two algorithms for the same task (e.g. search):
- AlgC: has bounded worst-case complexity, e.g. O(n.logn)
- AlgH: is a heuristic algorithm that is experimentally faster than AlgC, but there is no tight complexity bound for AlgH.
If we want to have an algorithm that is FAST but also has a guaranteed computational complexity, we can use some simple tricks. For example:
- We can run AlgC and AlgH simultaneously in an interleaved fashion (or in parallel), and once any of them finishes the task, we stop the other one. This ensures that AlgC binds the complexity, while the execution is as fast as AlgH.
- We can also run AlgH for a limited time (e.g. a factor of $n.\log n$) and if it hasn't finished, we run AlgC.
What are such techniques called in Algorithm's community? There should be a proper term for that, right?