6.6. Complexity Analysis

Try these first

1. 1.

   What is a requirement for two matrices to be multiplied?

   Hint

   Think about the dimensions of both matrices.

2. 2.

   What is the computational cost of multiplying a 5x3 matrix with a 3x2 matrix?

   Hint

   Use the formula: rows_A * cols_A * cols_B.

3. 3.

   How many computations does it take to multiply matrices A (m x n) and B (n x p)?

   • O(m*n*p)
   • O(n)
   • O(m+n)

   Hint

   Consider the dimensions' multiplication in your calculations.

4. 4.

   True or False: Matrix multiplication is commutative.

   • True
   • False

   Hint

   Think about matrix properties and examples to support your answer.

5. 5.

   Calculate the minimum number of multiplications needed for matrices A (10x100), B (100x5), C (5x50), D (50x200) using dynamic programming principles.

   Hint

   Evaluate each combination to find the least expensive set of operations.

6. 6.

   Describe how the choice of multiplication order impacts the dimensions of intermediate matrices and the overall cost. Give an example with specific sizes.

   Hint

   Illustrate using dimensions and remember that earlier combinations can lead to bigger matrices.