Matrix arithmetic in R Programming - Time & Space Complexity

Time Complexity: Matrix arithmetic

O(n^3)

Understanding Time Complexity

When working with matrices, it is important to know how the time to do calculations grows as the matrix size increases.

We want to understand how the number of steps changes when we multiply two matrices.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Multiply two square matrices A and B of size n x n
matrix_multiply <- function(A, B) {
  n <- nrow(A)
  C <- matrix(0, n, n)
  for (i in 1:n) {
    for (j in 1:n) {
      for (k in 1:n) {
        C[i, j] <- C[i, j] + A[i, k] * B[k, j]
      }
    }
  }
  return(C)
}
    

This code multiplies two square matrices by calculating each element of the result matrix using three nested loops.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Multiplying and adding elements inside three nested loops.
• How many times: The innermost operation runs once for every combination of i, j, and k, which is n x n x n times.

How Execution Grows With Input

As the matrix size n grows, the number of operations grows much faster because of the three loops.

Input Size (n)	Approx. Operations
10	1,000
100	1,000,000
1000	1,000,000,000

Pattern observation: When n increases by 10 times, the operations increase by 1000 times, showing a cubic growth.

Final Time Complexity

Time Complexity: O(n^3)

This means the time to multiply two n by n matrices grows roughly with the cube of n.

Common Mistake

[X] Wrong: "Matrix multiplication takes time proportional to n squared because the result is an n by n matrix."

[OK] Correct: Each element requires summing over n multiplications, so the total work is n x n x n, not just n x n.

Interview Connect

Understanding how matrix multiplication scales helps you reason about performance in many data and graphics tasks, showing you can think about efficiency clearly.

Self-Check

"What if we used a more advanced algorithm that reduces the number of multiplications? How would the time complexity change?"

Practice

1. In R, what does the operator %*% do when applied between two matrices?

easy

A. Performs matrix multiplication following linear algebra rules

B. Adds the two matrices element-wise

C. Subtracts the second matrix from the first element-wise

D. Multiplies the two matrices element-wise

Solution

1. Step 1: Understand matrix operators in R

   In R, + and - perform element-wise addition and subtraction respectively, while %*% is used for matrix multiplication.

2. Step 2: Identify the role of %*%

   The operator %*% multiplies matrices according to linear algebra rules, not element-wise.

3. Final Answer:

   Performs matrix multiplication following linear algebra rules -> Option A

4. Quick Check:

   %*% = matrix multiplication [OK]

Hint: Remember: %*% means matrix multiplication, not element-wise [OK]

Common Mistakes:

• Confusing %*% with element-wise multiplication
• Thinking + or - does matrix multiplication
• Using * for matrix multiplication

2. Which of the following is the correct way to create a 2x2 matrix with values 1, 2, 3, 4 in R?

easy

A. matrix(1, 2, 3, 4, 2, 2)

B. matrix(1, 2, 3, 4, nrow=2, ncol=2)

C. matrix(c(1, 2, 3, 4), rows=2, cols=2)

D. matrix(c(1, 2, 3, 4), nrow=2, ncol=2)

Solution

1. Step 1: Recall matrix creation syntax in R

   The function matrix() takes a vector of values and parameters nrow and ncol to specify dimensions.

2. Step 2: Check each option

   matrix(c(1, 2, 3, 4), nrow=2, ncol=2) correctly uses c(1, 2, 3, 4) and named arguments nrow=2, ncol=2. matrix(1, 2, 3, 4, nrow=2, ncol=2) has wrong argument format. matrix(c(1, 2, 3, 4), rows=2, cols=2) uses invalid argument names. matrix(1, 2, 3, 4, 2, 2) uses positional arguments without the vector wrapper.

3. Final Answer:

   matrix(c(1, 2, 3, 4), nrow=2, ncol=2) -> Option D

4. Quick Check:

   Use c() vector and nrow, ncol named args [OK]

Hint: Always wrap values in c() and name nrow, ncol [OK]

Common Mistakes:

• Not using c() to combine values
• Using wrong argument names like rows or cols
• Passing values without vector wrapper

3. What is the output of the following R code?

m1 <- matrix(c(1, 2, 3, 4), nrow=2, ncol=2, byrow=TRUE)
m2 <- matrix(c(5, 6, 7, 8), nrow=2, ncol=2, byrow=TRUE)
m3 <- m1 + m2
print(m3)

medium

A. [1 2; 3 4]

B. Error: non-conformable arrays

C. [6 8; 10 12]

D. [5 6; 7 8]

Solution

1. Step 1: Understand element-wise addition

   Using + between matrices adds corresponding elements: (1+5), (2+6), (3+7), (4+8).

2. Step 2: Calculate each element

   Results: 6, 8, 10, 12 arranged in 2x2 matrix.

3. Final Answer:

   [6 8; 10 12] -> Option C

4. Quick Check:

   Element-wise addition = sum of each element pair [OK]

Hint: Use + for element-wise addition, add each element pair [OK]

Common Mistakes:

• Expecting matrix multiplication instead of addition
• Confusing matrix dimensions causing errors
• Misreading matrix layout in output

4. Consider this R code snippet:

m1 <- matrix(c(1, 2, 3, 4), nrow=2)
m2 <- matrix(c(5, 6, 7), nrow=3)
m3 <- m1 %*% m2
print(m3)

What is the problem with this code?

medium

A. The matrices have incompatible dimensions for multiplication

B. The matrix m1 is not square

C. The operator %*% is invalid for matrices

D. The matrix m2 has missing values

Solution

1. Step 1: Check matrix dimensions

   m1 is 2x2, m2 is 3x1 (since 3 values and nrow=3). For multiplication, columns of m1 (2) must equal rows of m2 (3).

2. Step 2: Identify dimension mismatch

   2 != 3, so multiplication is not possible, causing an error.

3. Final Answer:

   The matrices have incompatible dimensions for multiplication -> Option A

4. Quick Check:

   Matrix multiplication needs matching inner dimensions [OK]

Hint: Check if m1 columns = m2 rows before multiplying [OK]

Common Mistakes:

• Assuming any matrices can be multiplied
• Ignoring dimension mismatch errors
• Thinking %*% works element-wise

5. You have two matrices in R:

m1 <- matrix(c(1, 0, 2, -1), nrow=2)
m2 <- matrix(c(3, 1, 4, 2), nrow=2)

You want to compute the matrix product m1 %*% m2 and then subtract the identity matrix of size 2. Which code correctly does this?

hard

A. m3 <- m1 * m2 - diag(2)

B. m3 <- m1 %*% m2 - diag(2)

C. m3 <- m1 %*% m2 - matrix(1, 2, 2)

D. m3 <- m1 %*% m2 - identity(2)

Solution

1. Step 1: Compute matrix multiplication

   Use %*% to multiply m1 and m2 correctly.

2. Step 2: Subtract identity matrix

   Use diag(2) to create a 2x2 identity matrix and subtract it from the product.

3. Final Answer:

   m3 <- m1 %*% m2 - diag(2) -> Option B

4. Quick Check:

   Use diag() for identity matrix in subtraction [OK]

Hint: Use diag(n) for identity matrix, %*% for multiplication [OK]

Common Mistakes:

• Using * instead of %*% for multiplication
• Using matrix(1,2,2) which is all ones, not identity
• Using identity() which is not an R base function