How quickly can you multiply a matrix by an matrix, using Strassen’s algorithm as a subroutine? Answer the same question with the order of the input matrices reversed.
Let us assume and are two matrices such that: and
Hence, is a matrix equal to , where each product is a matrix.
We can calculate each product using Strassens’s algorithm in time and there are such matrices. Hence, we can compute in time.
If we reverse the order of the input matrices, we are basically calculating , which is a matrix equal to .
In this case we need to perform matrix multiplication of matrices using Straseen’s algorithm and additions to add those products. Hence, we can compute in time.