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?

  • 3
    $\begingroup$ en.wikipedia.org/wiki/Dovetailing_(computer_science) $\endgroup$ – D.W. Sep 2 '19 at 16:47
  • $\begingroup$ @D.W. Thanks. Apparently, the term "dovetailing" mostly appears in the Turing machine textbooks but is not common in algorithms and other communities. $\endgroup$ – Ali Sep 2 '19 at 18:15

Hybrid algorithms.

In sorting algorithms it's rather common, Start with quicksort and if the size of the array is small enough switch to insertion sort (much faster for small $n$). Additionally when the recursion depth becomes too large (threatens to become $O(n^2)$) fall back to heapsort (guaranteed $O(n\log n)$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.