Cell array creation in MATLAB - Time & Space Complexity

Time Complexity: Cell array creation

O(n)

Understanding Time Complexity

We want to understand how the time needed to create a cell array changes as the size grows.

How does the work increase when we make bigger cell arrays?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

n = 1000;
C = cell(1, n);
for i = 1:n
    C{i} = i^2;
end

This code creates a cell array of size n and fills each cell with the square of its index.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that runs from 1 to n.
• How many times: Exactly n times, once for each cell assignment.

How Execution Grows With Input

Each time we increase n, the loop runs more times, doing more assignments.

Input Size (n)	Approx. Operations
10	10 assignments
100	100 assignments
1000	1000 assignments

Pattern observation: The work grows directly with n; doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to create and fill the cell array grows in a straight line with the number of cells.

Common Mistake

[X] Wrong: "Creating a cell array is instant and does not depend on size."

[OK] Correct: Even though the cell array structure is created quickly, filling each cell with data takes time proportional to the number of cells.

Interview Connect

Understanding how loops affect time helps you explain and improve code that handles collections like cell arrays.

Self-Check

"What if we preallocate the cell array but fill only half of the cells? How would the time complexity change?"