For many problems, the algorithm with the best asymptotic complexity has a very large constant factor that is hidden by big O notation. This occurs in matrix multiplication, integer multiplication (specifically, the recent O(n log n) integer multiplication algorithm of Harvey and van der Hoeven), low-depth sorting networks and finding graph minors, to make a few. Such algorithms are sometimes called Galactic algorithms.

Note that for other algorithms, such as general sorting and integer addition, algorithms are known with optimal asymptotic complexity and small constant factors.

What research has been done in separating the former algorithms from the latter algorithms, from a theoretical perspective?

I am aware that hidden constants are often omitted to hide the distinction between different models of computation. However, I am confident that under a wide variety of different models, these Galactic algorithms will be slower than asymptotically worse algorithms for inputs of size one billion, for instance. The distinction is not subtle, in some cases. Has it been made rigorous?

For instance, one could invent a very simple model of computation, such as a von Neumann machine with a very simple ISA, and then implement the algorithms and bound their running times with explicit constants. Has this been done for a variety of algorithms?

  • 1
    $\begingroup$ Fast integer multiplication algorithms are not galactic. They are actually commonly used in practice. $\endgroup$ Jul 11 '19 at 6:36
  • 3
    $\begingroup$ @EmilJeřábek May be the OP is talking about the recent breakthrough of David Harvey and Joris van der Hoeven, "Integer multiplication in $O(n \log n)$ time", which is galactic (see this this entry of Lipton's blog for example: rjlipton.wordpress.com/2019/03/29/… ) $\endgroup$
    – Lamine
    Jul 11 '19 at 8:20
  • 1
    $\begingroup$ As the authors write themselves (and is mentioned on Lipton’s blog), the paper for simplicity does not try to optimize the constants, but they very likely can be made practical. $\endgroup$ Jul 11 '19 at 8:28
  • $\begingroup$ @EmilJeřábek That paper was indeed the one I was talking about. The paper does describe improvements that could be made, but it is extremely doubtful that the algorithm as is will ever be a practical improvement over current O(n log n log log n) algorithms that are used in practice, given how small log log n is for practical inputs. $\endgroup$
    – isaacg
    Jul 11 '19 at 17:52
  • 4
    $\begingroup$ @EmilJeřábek Specifically, the algorithm presented in the paper defers to a simpler algorithm for a base case whenever the number has less than $2^{d^{12}}$ bits, where they currently take $d=1729$. The optimizations they describe might allow them to use $d=9$ instead, but $2^{9^{12}}$ bits still exceeds the number of particles in the universe, so practicality is still out of the question. See Section 5.4 of their paper. $\endgroup$
    – isaacg
    Jul 11 '19 at 17:59

One place where this is approached in an interesting way for a certain class of algorithms and combinatorial problems is in analytic combinatorics. The main approach described is similar to what you suggest: you start with some concrete implementation of an algorithm and identify some repeated operation (typically the heaviest one) that you'll use to associate an explicitly countable complexity for the execution of input of a given size $N$ in the form of the number $C_N$ that the chosen operation is performed.

The methodology does not require to fix any specific model of computation, although that could be useful of course. Also note that you could either try to compute the worst case behavior or the expected behavior, or still something else.

The most important ingredient in this methodology is the analysis of the generating functions of these values. You can sometimes obtain very precise asymptotic approximations using methods from complex analysis.

A simple example that is treated in the book is quicksort. This has a quadratic worst case running time, but in practice outperforms most $\mathcal O(n\log n)$ algorithms. When making a precise analysis of the expected cost of quicksort and you compare it to mergesort, you see that it is expected to outperform the latter from a size of around 10, if I remember correctly. To be able to compute this kind of things you cannot disregard the hidden constants of course.

In fact, in quicksort you sort a list by recursively sorting sublists, so that you would get an improvement for all sizes if you use mergesort on lists smaller than size 10. An interesting note in the book mentions that in some open sourced Microsoft library, the generic sort algorithm is implemented as quicksort until you get down to a size of 10, after which mergesort is used. In the code comments it is mentioned that performance tests showed this value to be optimal.


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.