Amazon Interview Question
Software Engineer / Developers@mayank Strassen's is not O(n), its O(n^2.8) and it is still considered as the lower bound for matrix multiplication.
Strassen's is definitely better than the standard matrix mmultiplication which is (n^3)
I think solution lies with creating adjacency list of two matrix and then using O(L1*L2)
- Anonymous June 10, 2010loop over them to calculate new non-zero element which results from multiplying them where L1 and L2 are no. of non-zero element in two matrices respectively.
This is the simplest solution we can achive i hope someone post more faster way.