6. (15 pts.] Your friend came up with an idea to rank pages on the web. The idea essentially boils down to computing the matric 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 (nxn) identity matrix, which has value 1 for its diagonal elements, and 0 everywhere else. Denote by A[i][j] = dij 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: 1 new 2-dimensional array of size (n xn) 2: for it to n-1 do 3: for j o to n - 1 do 4: 10] +0 5: Tilli] +1 6: return I Algorithm 6 SQUAREMATRIX MULT(A, B, n) 1: C + new 2-dimensional array of size (n xn) 2: for it to n-1 do 3: for j+0 ton - 1 do C[i][j] +0 for k to n - 1 do C[i][j] + C[i][j] + A[i][k] * B[k] [j] 7: return C Algorithm 7 MATRIX Pow1(A, n,m) 1: B + IDENTITYMATRIX(n) 2: for kr 1 to m do 3: B SQUAREMATRIX MULT(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 + MATRIX Pow2(A, n, 1) 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 6. (15 pts.] Your friend came up with an idea to rank pages on the web. The idea essentially boils down to computing the matric 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 (nxn) identity matrix, which has value 1 for its diagonal elements, and 0 everywhere else. Denote by A[i][j] = dij 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: 1 new 2-dimensional array of size (n xn) 2: for it to n-1 do 3: for j o to n - 1 do 4: 10] +0 5: Tilli] +1 6: return I Algorithm 6 SQUAREMATRIX MULT(A, B, n) 1: C + new 2-dimensional array of size (n xn) 2: for it to n-1 do 3: for j+0 ton - 1 do C[i][j] +0 for k to n - 1 do C[i][j] + C[i][j] + A[i][k] * B[k] [j] 7: return C Algorithm 7 MATRIX Pow1(A, n,m) 1: B + IDENTITYMATRIX(n) 2: for kr 1 to m do 3: B SQUAREMATRIX MULT(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 + MATRIX Pow2(A, n, 1) 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