Consider the following pseudocode divide-and-conquer implementation of square matrix multiplication. SQUARE-MATRIX-MULTIPLY-RECURSIVE(A, B) 1 n = A.rows 2 let C be a new n x n matrix 3 if n == 1 4 Cu = dubu 5 else partition A, B, and C as in equations (4.9) 6 Cu = SQUARE-MATRIX-MULTIPLY-RECURSIVE(Au, Bu) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12, B21) 7 C12 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A11, B12) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12, B22) C21 SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21, Bu) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22, B21) 9 C22 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21, B12) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22, B22) 10 return C 8 The matrix partition is defined as follows: Suppose that we partition each of A, B, and C into four n/2 x n/2 matrices Au A12 Bu B12 Cu C12 A= C = (4.9) A21 A22 B21 B22 C2 C22 so that we rewrite the equation C = A B as Cu C12 Au A12 Bu B12 (4.10) C2 C22 A21 A22 B21 =( B = ( ). =( Use a recursion tree to show that this implementation has time complexity 0(n3). Consider the following pseudocode divide-and-conquer implementation of square matrix multiplication. SQUARE-MATRIX-MULTIPLY-RECURSIVE(A, B) 1 n = A.rows 2 let C be a new n x n matrix 3 if n == 1 4 Cu = dubu 5 else partition A, B, and C as in equations (4.9) 6 Cu = SQUARE-MATRIX-MULTIPLY-RECURSIVE(Au, Bu) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12, B21) 7 C12 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A11, B12) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12, B22) C21 SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21, Bu) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22, B21) 9 C22 = SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21, B12) + SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22, B22) 10 return C 8 The matrix partition is defined as follows: Suppose that we partition each of A, B, and C into four n/2 x n/2 matrices Au A12 Bu B12 Cu C12 A= C = (4.9) A21 A22 B21 B22 C2 C22 so that we rewrite the equation C = A B as Cu C12 Au A12 Bu B12 (4.10) C2 C22 A21 A22 B21 =( B = ( ). =( Use a recursion tree to show that this implementation has time complexity 0(n3)