) Algorithm 5 IDENTITYMATRIX(12) 11 new 2 dimensional array of size (X 2: for i Oton- I do 3 for j o ton- I do 1000 5 71441 6 return Ilowki CIS 350: Data Structures and Algorithm Analysis ) Algorithm 6 SQUAREMATRIX MULT(A, B,) 1: C new 2-dimensional array of sine (n X 2. for i Oton-1 do for jo ton- I do CH -0 for k o to n-1 do CGT-CGT + A + BIG return C Algorithm 7 MATRIX Powl(A,1,m) 1B MENTITYMATRIX(R) 2 for k1 to n do * B-SQUAREMATRIX MULT(B,A,n) 4 return B Algorithm 8 MATRIX Pow2(A,,m) 1. if m=0 then return IDENTITYMATRIX() 2: Ifm I then return A # B MATRIX Pow2(A,n,11 ABSQUAREMATRIX MULT(B, B, ) & If mis odd then 6 B-SQUAREMATRIX MULT(B,A,n) return B (a) Give the tightest running time and space characterization using Big Oh and Big Omegn or Big-Theta, of MATRIX Pow1(A, 1, n) in terms of n. Briefly justify your answer. (Note that mon in the initial function call) Time (1) Give the tightest running time and space characterization using Big Oh and Big Om or Big-Theta, of MATRIX Pow2(A,,) in terms of Briefly justify your answer. (Note that m=r in the initial function call) Space (c) Give the tightest characterization using Big Oh and Big Omega, or Big-Theta, of the input size N in terms of , assuming that m = n in the initial function call. Briefly justify your answer. STICE Page 10 of 11 Homework 1 CIS 350: Data Structures and Algorithm Analysis Winter 2020 (d) Give the tightest running time and space characterization using Big Oh and Big Omega or Big-Theta, of MATRIXPowl(A., n) in terms of the input size N. Briefly justify your answer. (Note that in the initial function call) Time (d) Give the tightest running time and space characterization using Big Oh and Big Omega or Big-Theta, of MATRIX Powl(A, n, n) in terms of the input size N. Briefly justify your answer. (Note that in the initial function call) me Space (e) Give the tightest running time and space characterization using Big Oh and Big Omega, or Big Theta, of MATRIX Pow2(4,7, n) in terms of the input size N. Briefly justify your answer. (Note that m= n in the initial function call) Time SO