3 ms·
Isn’t multiplying two 4x4 matrices a finite problem? What does big O complexity mean in that case?
by skybrian 4y ago
Isn’t multiplying two 4x4 matrices a finite problem? What does big O complexity mean in that case?
- adgjlsfhk1 4y agoany fixed size multiplication algorithm has a corresponding general algorithm where you recursively divide a matrix into blocks and treat each block as an element. for any nxn algorithm that takes k multiplications, this yields a general algorithm with runtime n^log_n(k)
- Rioghasarig 4y agoMy understanding of this situation is that they found a way to multiply 4x4 matrices that requires fewer multiplications than Strassen's . This implies that that can generalize to a way to multiply n x n matrices with a better theoretical complexity than Strassen's algorithm.