1. (12 points total) Addition of two nn matrices can be done using n2 scalar additions. The most elementary method for multiplying two nn matrices involves computing the inner product of two length- n vectors for each entry in the output matrix; this method uses a total of n3 scalar multiplications and n2(n1)=(n3) scalar additions. In the parts below, assume that n is a power of 2 . (a) (3 points) By partitioning each nn matrix into four 2n2n submatrices, it is straightforward to verify that two nn matrices (with n2 ) can be multiplied using 8 multiplications of 2n2n matrices and 4 additions of 2n2n matrices. This idea yields a divide-and-conquer algorithm for matrix multiplication. Write a suitable recurrence for upper bounding the total number of scalar operations (additions or multiplications) performed by this algorithm. You do not need to justify your recurrence. (b) (3 points) Solve your recurrence of part (a) by stating a best-possible O-bound on the total number of scalar operations. If your final answer is correct, you will receive full credit. (If your final answer is incorrect and you show your work, you might receive partial credit.) (c) (3 points) A more sophisticated method for multiplying two nn matrices (with n2 ) uses 7 multiplications of 2n2n matrices and 15 additions of 2n2n matrices. As in part (a), write a recurrence for upper bounding the total number of scalar operations performed by the associated divide-and-conquer algorithm. You do not need to justify your recurrence. (d) (3 points) Solve your recurrence of part (c) by stating a best-possible O-bound on the total number of scalar operations. If your final answer is correct, you will receive full credit. (If your final answer is incorrect and you show your work, you might receive partial credit.)