need help

3. Recursive Algorithm and Analysis (6 points) Suppose company X has hired you as a software engineer. The bigwigs at company X heard about how Divide and Conquer can be used to improve the runtime of matrx multiplication. Thus, rather than allow you to use the standard matrix addition algorithm, they want you to also create a Divide and Conquer algorithm to add matrices. Reminder: Suppose your input matrices are A and B. Likewise suppose your output matrix is C. Specifically for all i,j your code computes C[i][j]= A[i][j]+B[i][j]. You can assume A,B, and C are all nn matrices and, for simplicity, that n is a power of 2 . (1) (2 points) Identify the Divide, Conquer, and Combine steps of your new algorithm. (Note: a one sentence explanation of each is fine; see notes for examples). (2) (1 point) Create a recurrence to represent the runtime of your new algorithm. (3) (2 points) Use master theorem to solve your above recurrence relation. Compare this asymptotic run time to the standard O(n2) matrix addition algorithm. (4) (1 point) Do you think there's a trick like Strassen's to improve the asymptotic runtime of your Divide and Conquer matrix addition algorithm? Justify why or why not