Read on Twitter
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 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
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)
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
Therefore Coppersmith–Winograd algorithm comes under the galactic algorithm category
If you are interested in reading about more such problems
you should consider giving this a read
https://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/
Happy Algorithming!!!
you should consider giving this a read
https://rjlipton.wordpress.com/2010/10/23/galactic-algorithms/Happy Algorithming!!!
