Sorting Algorithms Consider A Matrix Multiplication Computation Program C = B*(A +D) Where A, B, C, And D Are (Nxn) Two-Dimensional Matrices. Ans =? Time Complexity Of Matrix Addition A + D = O(N2) Time Complexity Of Matrix Multiplication B*(A + D) = O(N3) So, Total Complexity Of Operation C = B*(A + D)

1. Consider a matrix multiplication computation program C = B*(A +D) where A, B, C, and D are (nxn) two-dimensional matrices.

Ans => Time complexity of matrix addition A + D = O(n²)

Time complexity of matrix multiplication B*(A + D) = O(n³)

So, total complexity of operation C = B*(A + D) is

= O(n²) + O(n³)

= O(n³)

1. The program is executed on a computer with the following characteristics:
1. CPU time for one multiplication is 100 microseconds
2. CPU time for one addition is 5 microseconds
3. The memory reference time for either read or write is 200 microseconds
2. Let n=1000, what is the total time required to perform the multiplication. Assume that all data is located in memory.

• Ans => As we can see above time complexity for multiplication is O(n³).

So, n = 1000.

N³= 1000³= 1000,000,000

Performing one multiplication requires = 100 microseconds

• N³* 100 microseconds 100,000,000,000 microseconds.
• 100,000 seconds Approx. 1667 minutes Approx. 28 hours.

1. What is the space complexity for this problem

• Ans => O(N²).

1. Now assume that you run the program on a computer with the following characteristics
1. CPU time for one multiplication is 500 microseconds
2. CPUT time for one addition is 1 microsecond
3. The memory reference time for either read or write is 100 microseconds
2. Let n=1000, what is the total time required to perform the multiplication. Assume that all data is located in memory (5)

• Ans => Only difference here is time for one multiplication is 500 microseconds. Complexities are the same.

• N³* 500 microseconds.
• 500,000,000,000 microseconds Approx. 139 hours.

1. What is the space complexity for this problem (5)

• Ans => The space complexities would be the same because the number of performance and items were playing with is the same.

1. Given the results for the above two scenarios, what is the time complexity for the matrix multiplication code?

• Ans => O(n³)

1. Now assume that you have 1000 processors available for the program execution. Each processor has a local memory, large enough to accommodate the problem.
1. what is the total time required to perform the multiplication using 1000 processors.

• Ans => When multiple processors(parallel computers) are used for program execution, the number of operations will be divided between processors for efficiency, yet the complexity stays the same regardless the number of processors.

• 100,000,000 microseconds 100 seconds Approx. 1.67 minutes.
• 500,000,000 microseconds 500 seconds Approx. 8 minutes.

1. What is the space complexity for this case?

• Ans => As I said above, the large number of processors will speed up the time to get results faster, but the complexities are independent from number of processors used. So, the space complexity stays the same. O(n²).

1. What is the time complexity for this case?

Ans => We are using (nxn) matrices. The time complication for multiplication for (nxn) matrices is O(n³). Parallel computer reduces the clock time, but it doesnt affect the time complexity.

1. What is the speedup for the system, when 1000 processors are used (5)

Ans => Its a lot faster, previously the execution would have taken approximately 28 hours when processor speed was 100 microseconds per each computation and 139 hours when speed was 500 microseconds for single multiplication. Using 1000 processors, we reduced them to approx. 1.67 minutes and 8 minutes respectively.

Speedup = (100,000,000 s / 100 s) 1000x speed up.

Same applies to the both scenarios.

1. What is the absolute minimum complexity for this problem assuming infinitely large number of processors?

• Answer this question.

1. What is the minimum number of processors required to achieve the absolute minimum complexity (5)

• Answer this question.

1. What is the space complexity for the minimum time complexity case (2)

• Answer this question.

1. Why is it not practical to measure the time complexity of sorting and search algorithms in terms of actual execution time?

• Ans =>Its not practical because time complexity is independent of execution time. Time complexity is the theoretical concept, whereas execution time refer to how long does it take to run the program and can be measured using stopwatch or anything.

\"Could you please check my answers and correct them if they are wrong, and answer question 10, 11, and 12 based on the previous answer\"