2. Consider the following procedure that performs multiplication of two lower triangular matrices A[1..n][1..n] and B[1..n][1..n]. MATRIX_MULTIPLY (A[1..n][1..n], B[1..n][1..n]) Run-time per instruction Frequency for i 1 to n for j1 to

i 1. 2. 3. 4. 5. 6. Cij ←0 for kj to i return C Cij ←cij +aik bkj 553338 C₁ C3 C4 C5 C6 As the product C[1..n][1..n] is also lower triangular, we assume that we do not have to be concerned with the strictly upper triangular entries of the matrix, which are all zeros. (a) Fill in for each line of instruction, the number of times (i.e., frequency) the instruction is executed. (b) Derive the expression for the run-time of MATRIX MULTIPLY in terms of n and C₁, C2, C3, C4, C5, and C6- In your expression, you should group together all the coefficients of the same term n¹, where i is a constant. For example, if the run-time expression is C4n² + +n+C5n²+ Con+C₂, we group the coefficients of n² together, the coefficients of n¹ together, and the coefficients of nº together. Note that each of n², n¹, and nº involves the parameter "describing" the problem, i.e., n. The final expression should be (C4+C5)n²+(+6)n +(+C₂).