Ever heard of this term "Galactic Algorithm"?

This name is given to algorithms that have good asymptotic behavior but would never be used in practice

Why?? https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">

This is because they run comparatively faster for problems that are sufficiently large, but these problems are so big that the algorithm is never used.

For instance in Matrix multiplication problem the first ever algorithm which improved O(N^3) is Strassen algorithmhttps://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">

Strassen algorithm is a recursive algorithm that is proved to achieve matrix multiplication in O(N^2.807)

Further improvements were done in Coppersmith–Winograd algorithm which achieved O(N^2.373) https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">

This first one is used in practice but the latter i.e Coppersmith–Winograd algorithm cannot because of the huge constants involved.

Therefore Coppersmith–Winograd algorithm comes under the galactic algorithm category https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">

If you are interested in reading about more such problems
you should consider giving this a readhttps://abs.twimg.com/emoji/v2/... draggable="false" alt="👉" title="Rückhand Zeigefinger nach rechts" aria-label="Emoji: Rückhand Zeigefinger nach rechts"> https://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/

Happy">https://rjlipton.wordpress.com/2010/10/2... Algorithming!!!https://abs.twimg.com/emoji/v2/... draggable="false" alt="😎" title="Lächelndes Gesicht mit Sonnenbrille" aria-label="Emoji: Lächelndes Gesicht mit Sonnenbrille">