3. Consider the Strassen's matrix multiplication algorithm (a divide and conquer approach). (1) Using traditional matrix product method, how many multiplications and additions do we need to multiply...

16Alg_3

Please answer the following question step by step

Extracted text: 3. Consider the Strassen's matrix multiplication algorithm (a divide and conquer approach). (1) Using traditional matrix product method, how many multiplications and additions do we need to multiply two 2x2 matrices? How about Strassen's method? (2)Write down the related recurrence equation, and give the asymptotic tight bound solution. (3)Suppose that we use a similar divide and conquer approach to compute this problem; divide nxn matrices into submatrics the same way as Strassen's ,while in the 2 2 "merge" part, there are m submatrix multiplications and a submatrix additions. Find the time complexity of this method.