Hacker News new | ask | show | jobs
by 3pac 1034 days ago
Where does 2.73 come from?
1 comments

Naive method is O(n^3).

Strassen algorithm drops it to O(n^log2(7)) = 2.8074 because it divides the process into 2x2 matrix multiplications that can be multiplied by 7 ops instead of 8. Strassen is practical algorithm.

You can still optimize and get to 2.371552 with complex trickery, but these are galactic algorithms, meaning that matrices are so big that you can't even construct them on Earth.