Special matrices (zeros, ones, eye, rand) in MATLAB - Time & Space Complexity

Time Complexity: Special matrices (zeros, ones, eye, rand)

O(n^2)

Understanding Time Complexity

When creating special matrices like zeros, ones, eye, or rand in MATLAB, it's important to know how the time to create them grows as the matrix size increases.

We want to understand how the work done changes when the matrix gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

n = 1000;
A = zeros(n, n);
B = ones(n, n);
C = eye(n);
D = rand(n, n);

This code creates four special matrices of size n by n: all zeros, all ones, identity, and random values.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Filling each element of the n by n matrix.
• How many times: Each matrix has n * n elements, so the operation repeats n squared times.

How Execution Grows With Input

As the matrix size n grows, the number of elements grows by n squared, so the work grows quickly.

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

Pattern observation: Doubling n makes the work about four times bigger because the matrix has n squared elements.

Final Time Complexity

Time Complexity: O(n^2)

This means the time to create these matrices grows proportionally to the square of the matrix size.

Common Mistake

[X] Wrong: "Creating these matrices takes time proportional to n, not n squared."

[OK] Correct: Each matrix has n rows and n columns, so the total elements are n times n, which is n squared. The computer must set each element, so the time grows with n squared.

Interview Connect

Understanding how matrix creation time grows helps you reason about performance in data processing and simulations, which is a useful skill in many programming tasks.

Self-Check

"What if we create a vector instead of a matrix, like zeros(n, 1)? How would the time complexity change?"