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?? 👇
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 algorithm👇
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) 👇
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 👇
You can follow @apoorv__tyagi.
Tip: mention @twtextapp on a Twitter thread with the keyword “unroll” to get a link to it.

Latest Threads Unrolled: