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 x n) matrix, its mth power is A"; that is, multiplying the matrix A by itself m times, where, by definition, A = I, the (n x n) identity matrix, which has value 1 for its diagonal elements, and 0 everywhere else. Denote by A[i][j] 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 x n) matrix B whose elements correspond to those of the matrix B = 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 SQUAREMATRIXXMULT, also given below. %3D aij the element in Am. Assume that all the arrays are Algorithm 5 IDENTITYMATRIX(n) 1: I+ new 2-dimensional array of size (n n) 2: for i + 0 to n 1 do for j+0 to n I(i][j] + 0 I (i] [e] 1 do 3: 4: 5: 6: return I Algorithm 6 SQUAREMATRIXMULT(A, B, n) 1: C + new 2-dimensional array of size (n x n) 2: for i +0 to n 1 do for j+0 to n 1 do C[i][j] + 0 for k +0 ton 1 do 3: 4: 5: C[i][G] + C[i][;] + A[i][k] * B[k][j] 6: 7: return C Algorithm 7 MATRIXPOW1(A, n, m) 1: B+ IDENTITYMATRIX(n) 2: for k + 1 to m do B+ SQUAREMATRIXMULT(B, A, n) 3: 4: return B Algorithm 8 MATRIXPOW2(A, n, m) 1: if m = 0 then return IDENTITYMATRIX(n) 2: if m = 1 then return A 3: + TRIPOW2(A, , [%) 4: + SQUARETRIXMULT(, , ) 5: if m is odd then B+ SQUAREMATRIXMULT(B, A, n) 6: 7: return B (a) Give the tightest running-time and space characterization using Big-Oh and Big-Omega, or Big-Theta, of MATRIXPOW1(A, n, n) in terms of n. Briefly justify your answer. (Note that m = n in the initial function call.) Space Time (b) Give the tightest running-time and space characterization using Big-Oh and Big-Omega, or Big-Theta, of MATRIXPOW2(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