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?"