A '''galactic algorithm''' is one that outperforms any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in practice. Galactic algorithms were so named by [[Richard Lipton]] and Ken Regan,<ref name="seminal">{{cite book |author=Lipton, Richard J., and Kenneth W. Regan |chapter=David Johnson: Galactic Algorithms |title=People, Problems, and Proofs |publisher=Springer Berlin |___location=Heidelberg |year=2013 |pages=109–112 |chapter-url=https://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/}}</ref> asbecause they will never be used on any data sets on Earth.
== Possible use cases ==
Line 42:
=== Minimum Spanning Trees ===
The [[Expectedexpected linear time MST algorithm|Karger-Klein-Tarjan]] algorithm is able to discover the [[Minimum spanning tree]] of a graph in <math>O(m + n)</math>, where <math>m</math> is the number of edges and <math>n</math> is the number of nodes of the graph.<ref>{{Cite journal |last=Karger |first=David R. |last2=Klein |first2=Philip N. |last3=Tarjan |first3=Robert E. |date=1995-03-01 |title=A randomized linear-time algorithm to find minimum spanning trees |url=https://doi.org/10.1145/201019.201022 |journal=Journal of the ACM |volume=42 |issue=2 |pages=321–328 |doi=10.1145/201019.201022 |issn=0004-5411}}</ref> However, the constant factor that is hidden by the [[Big O notation]] is huge enough to make the algorithm impractical. It'sAn implementation is publicly available<ref>{{Cite atweb [|last=Thiesen |first=Francisco |title=karger-klein-tarjan |url=https://github.com/FranciscoThiesen/karger-klein-tarjan here|access-date=2022-11-19 |website=[[GitHub]]}}</ref> and given the experimentally estimated implementation constants, it would only be faster than [[Borůvka's algorithm]] for graphs in which <math>m + n > 9 * 10^{151}</math>.<ref>{{Cite web |last=Geiman Thiesen |first=Francisco |title=Expected Linear-Time Minimum Spanning Trees |url=https://franciscothiesen.github.io/Linear-Time-MST/ |access-date=2022-11-13 |website=franciscothiesen.github.io}}</ref>
