Matrix transpose in MATLAB - Time & Space Complexity

Time Complexity: Matrix transpose

O(n^2)

Understanding Time Complexity

We want to understand how the time needed to transpose a matrix changes as the matrix gets bigger.

Specifically, how does the work grow when we swap rows and columns?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function B = transposeMatrix(A)
  [rows, cols] = size(A);
  B = zeros(cols, rows);
  for i = 1:rows
    for j = 1:cols
      B(j,i) = A(i,j);
    end
  end
end
    

This code creates a new matrix B that is the transpose of matrix A by swapping rows and columns.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Assigning each element from A to B in swapped position.
• How many times: The inner assignment happens once for every element in A, so rows x cols times.

How Execution Grows With Input

As the matrix size grows, the number of operations grows with the total number of elements.

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

Pattern observation: Doubling the size of each dimension squares the total work, because every element must be moved.

Final Time Complexity

Time Complexity: O(n^2)

This means the time needed grows with the square of the matrix dimension, since every element is processed once.

Common Mistake

[X] Wrong: "Transposing a matrix only takes O(n) time because we just swap rows and columns once."

[OK] Correct: Each element must be moved individually, so the work depends on the total number of elements, which is n x n, not just n.

Interview Connect

Understanding how matrix operations scale helps you reason about performance in many real-world tasks like image processing or data transformations.

Self-Check

"What if we only transpose a sparse matrix where most elements are zero? How would the time complexity change?"