1
$\begingroup$

On the Wikipedia article for galactic algorithm (an algorithm that only becomes efficient when the inputs are so large that the algorithm is not used in practice), one of the use cases is that

Available computational power may catch up to the crossover point, so that a previously impractical algorithm becomes practical.

What are some examples of this happening?

I'm looking specifically for impractical algorithms that became practical because problem sizes got larger or computers got faster, and not because of improvements to the algorithm itself that made it practical.

Improve this question
$\endgroup$
3
  • $\begingroup$ If the problem size becomes larger, not sure this could make the computation more feasible? It seems only computers going faster could help? $\endgroup$
    – Frank
    May 19 at 18:21
  • $\begingroup$ @Frank The point, I think, is that a problem may get to be large enough that the "Galactic" algorithm is actually faster than the traditional algorithm. Yes, faster computers will be necessary, but at some point the GA is faster than the TA and we still switch since there's no point in wasting cycles. $\endgroup$
    – Mark Olson
    May 19 at 21:54
  • $\begingroup$ @MarkOlson OK, I see. $\endgroup$
    – Frank
    May 19 at 22:17

1 Answer 1

Reset to default
1
$\begingroup$

One example would be Strassen’s matrix multiplication algorithm which can be more efficient than the conventional $O(n^{3})$ algorithm for large enough matrices. Unfortunately, there are numerical stability issues that can make it unsuitable in many applications.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Strassen’s algorithm can save time even for quite small matrices. I don't think it was used immediately on its publication in 1969, but it would have been obvious from the beginning that it could be useful in practice. It doesn't have the huge hidden constant factors that galactic algorithms typically do. $\endgroup$
    – benrg
    4 hours ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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