## Question

1 n = A.rows

2 let C be a new n×n matrix

3 if n == 1

4 c11 = a11 · b11

5 else partition A, B, and C

6 C11 = Square-Matrix-Multiply-Recursive(A11, B11) +Square-Matrix-Multiply-Recursive(A12, B21)

7 C12 = Square-Matrix-Multiply-Recursive(A11, B12) +Square-Matrix-Multiply-Recursive(A12, B22)

8 C21 = Square-Matrix-Multiply-Recursive(A21, B11) +Square-Matrix-Multiply-Recursive(A22, B21)

9 C22 = Square-Matrix-Multiply-Recursive(A21, B12) +Square-Matrix-Multiply-Recursive(A22, B22)

10 return C

Since the matrices A and B is n × n matrices , they can be represented in regular arrays of size n2 . The coefficient Cij in matrix ( 0 - indexed) is accessed when the array a with a [ in + j] .

You will implement two versions , one that copies submatrix into new arrays , and one that uses two index variables to indicate which part of the array being worked on.

You must be reasoned you find one Recurrence equation for both editions , and explain why the same equation can be used to describe both. You should then make an analysis using rekursjonstrær so that you arrive at a guess for a function that describes the running time of the algorithm . This shall then verify both the substitution method ( mathematical induction) and masterteoremet .

Although copying edition has a higher cost than the index release both Editions same asymptotic notation. The difference is only one constant between the two editions when we analyze the running time . Is this also the case in practice? Test the two versions of the algorithm with different input sizes and judge it only distinguishes between a constant or not. Discuss the results and emphasize explain why it may not be true that it only distinguishes a constant.

Hints:

A[(n/2) * k + i, (n/2)m + j]

one square to split into four square

over left square: A11 k = 0 m = 0

over right square: A12 k = 0 m = 1

under left square: A21 k = 1 m = 1

under right square: A22 k = 1 m = 1

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

public class SquareMatrixMultiplyRecursive {public static int[] square_matrix_multiply_recursive_copy(int[] A, int[] B)

{

int[] C;

int n = A.length;

C = new int[n];

if(n == 1)

C[0] = A[0] * B[0];...