(d) 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 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 MATRIXPow2(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 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, []) 4: B + SQUAREMATRIX MULT(B, B, n) 5: if m is odd then 6: B+ SQUAREMATRIXMULT(B, A, n) 7: return B (d) 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 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 MATRIXPow2(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 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, []) 4: B + SQUAREMATRIX MULT(B, B, n) 5: if m is odd then 6: B+ SQUAREMATRIXMULT(B, A, n) 7: return B