To Expert: You dont actually need the past homework assignments to succeed in this homework.

The objective of this assignment is to analyze the time complexity of a simple algorithm to compute P=M * N where M and N is are nn matrices where M is a lower triangular matrix and N is an upper triangular matrix. MatrixProduot (M,N,n ) inputs: M is a lower triangular nn matrix. N is an upper triangular nn matrix n is an integer (n1) output: P is a nn matrix such that P=MN 1: for i=1 to n 2: for 2=1 to n sum =0 for k=1 to 1 5: sum = sum +M[1,k1+N[k,j1 7: return p[1,3]=stam Running Time of MatrixProduct ( 94 points) a. (2 points) What is the input size? b. (43 points) Count precisely the total number of additions C(n) performed by the for loop on Line 4 Express C(n) as a function of n. (Use the same steps we used in the previous lectures and homework assignments to analyze nested for loops. Use a table and steps like in Homework 1. Be as precise as Student 3 to get full credit (See Appendix) c. (2 points) What is the asymptotic bound for C(n) ? Be as precise as Student 3 to get full credit (See Appendix) d. (43 points) Count precisely the total number of multiplications E(n) performed by Line 5. Express E(n) as a function of n. (Use the same steps we used in the previous lectures and homework assignments to analyze nested for loops. Use a table and steps like in Homework 1. Be as precise as Student 3 to get full credit (See Appendix) e. (2 points) What is the asymptotic bound for E(n) ? Be as precise as Student 3 to get full credit (See f. (1 points) Which expression (C(n) ? or E(n)) yields the right asymptotic growth? Which expression ( C(n) or E(n) ?) is more convenient to derive the asymptotic growth of the running time of the MatrixProduct algorithm? 8. (3 points) Based on your previous answers, which operation (addition or multiplication) should you use to determine the time complexity of MatrixProduct. Space Complexity ( 6 points) a. (5 points) What is the space complexity of MatrixProduct? b. (1 point) is MatrixProduct an in place algorithm