3. Fast Matrix Multiplication. Given two n n matrices X, Y of integers, their product is another n n matrix Z with. Naively, computing Z seems to take O(n) time since there are n2 entries, and computing the value for a single entry involves n addition operations. In this problem, we'll develop a faster matrix multiplication algorithm. For simplicity, assume that n is a power of 2 (a) First, define eight n/2 x n/2 matrices A, B,C, D, E, F,G, H so that, E F G H Prove that Homework 3 1-2 (b) This suggests a divide and conquer algorithm for matrix multiplication. Describe the algorithm in words, write down the running time as a recurrence relation, and solve the recurrence. (c) The above algorithm uses eight recursive calls, but a more clever decomposition due to Strassen using only seven recursive calls of similar form. What is the recurrence can achieve the same result for such an algorithm and what would the running time be? You do not have to come up with the algorithm, but rather your task is to analyze the running time of an algorithm like the one above, but that only makes 7 recursive calls