Experiment 5 Part 1 The first algorithm is one method for co

Experiment 5

Part 1

The first algorithm is one method for computing the product of two n x n matrices. Assume that the matrices are each stored in an array of dimension 2 and that A[i, j] holds the element a A in row i and column j.

ALGORITHM: MATMUL (A, B, C)

1. FOR I = 1 THRU N

a. FOR J = 1 THRU N

1. C[I, J] (left pointing arrow) 0

2. FOR K = 1 THRU N

a. C[I, J] (left pointing arrow) C[I, J] + A[I, K] + B[K, J]

Assume that each assignment of a value, each addition , and each element multiplication take the same fixed amount of time.

1. How many assignments will be done in the second FOR loop?

2. How many element mulitplications are done in the third FOR loop?

3. What is the running time of MATMUL? Justify your answer.

Solution

1. There will be NXN assignment because C[I,J] is assigned N times and
Then . C[I, J] (left pointing arrow) C[I, J] + A[I, K] + B[K, J] again N times , So N*N = . N² TIMES.

2. N multiplication are done in 3rd for LOOP.

3.   What is the running time of MATMUL Is O(N³) Because there are three FOR loops Since each for loops runs N times . And The 1st for loop will run for Ntime , and The 2nd for loop will run for N²time [N times itself and N times because of Outer loop so N² ].  And The 3rd for loop will run for N³ time

So overall time for MATMUL is O(N³)



Thanks, let me know if there is any concern.