Please write legibly so I can learn from your work. Thank you!

6. (15 pts. Your friend came up with an idea to rank pages on the web. The idea essentially boils down to computing the matrix power to an arbitrary value m for m > 0: formally, if A is a square (n xn) matrix, its mth power is A"that is, multiplying the matrix A by itself m times, where, by definition, A = I, the (n xn) identity matrix, which has value 1 for its diagonal elements, and 0 everywhere else. Denote by Ai] = aij the element in row i and column j of the matrix A; similarly for other matrices. Your friend came up with several algorithms for you to analyze and provide a final recommendation as to which one to implement. The following is pseudocode for the various alternatives. They all take as input a 2-dimensional array of numbers A, each dimension of size n > 1, representing the matrix A, and the value m > 0 of the power of A to be computed. They all output an (n xn) matrix B whose elements correspond to those of the matrix B= A". Assume that all the arrays are passed by-value, that functions return a fullew copy of the output array, and that that array assignments also create a fullew copy of the array being assigned. The algorithms also use the auxiliary functions IDENTITYMATRIX and SQUAREMATRIX MULT, also given below. Algorithm 5 IDENTITYMATRIX(n) 1: I new 2-dimensional array of size (n xn) 2: for it to n - 1 do 3: for j o to n - 1 do 4: ILO 5: 1[i][i] +1 6: return I Algorithm 6 SQUAREMATRIX MULT(A, B, n) 1: C new 2-dimensional array of size (n xn) 2: for it 0 to n - 1 do 3: for j = 0 ton - 1 do C[i][j] = 0 5: for k o to n - 1 do Cilj + CU] + A[ ik] * Bk Lj] 7: return C Algorithm 7 MATRIXPow1(A, n,m) 1: B + IDENTITYMATRIX(n) 2: for kr 1 to m do 3: B SQUAREMATRIXMULT(B, A, n) 4: return B Algorithm 8 MATRIX Pow2(A, n,m) 1: if m=0 then return IDENTITYMATRIX(n) 2: if m= 1 then return A 3: B + MATRIXPow2(A, n, L]) 4: B SQUAREMATRIX MULT(B, B, n) 5: if m is odd then 6: B SQUAREMATRIX MULT(B, A, n) 7: return B (a) Give the tightest running-time and space characterization using Big-Oh and Big-Omega, or Big-Theta, of MATRIX Pow1(A, n, n) in terms of n. Briefly justify your answer. (Note that m= n in the initial function call.) Time Space (b) Give the tightest running-time and space characterization using Big-Oh and Big-Omega, or Big-Theta, of MATRIX Pow2(A, n, n) in terms of n. Briefly justify your answer. (Note that m = n in the initial function call.) Time Space (c) Give the tightest characterization using Big-Oh and Big-Omega, or Big-Theta, of the input size N in terms of n, assuming that m = n in the initial function call. Briefly justify your answer. Space (d) Give the tightest running-time and space characterization using Big-Oh and Big-Omega, or Big-Theta, of MATRIX Pow1(A, n, n) in terms of the input size N. Briefly justify your answer. (Note that m= n in the initial function call.) Time Space (e) Give the tightest running-time and space characterization using Big-Oh and Big-Omega, or Big-Theta, of MATRIX Pow2(A, n, n) in terms of the input size N. Briefly justify your answer. Note that m= n in the initial function call.) Time Space Space