Structures and field access in MATLAB - Time & Space Complexity

Time Complexity: Structures and field access

O(n)

Understanding Time Complexity

We want to understand how the time it takes to access data in a structure grows as the structure gets bigger.

Specifically, how does accessing fields in a MATLAB structure change with more data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

data = struct();
for i = 1:n
    data(i).value = i * 2;
end

for i = 1:n
    x = data(i).value;
end

This code creates a structure array with n elements, each having a field 'value'. Then it accesses each field once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the structure array to access the 'value' field.
• How many times: Exactly n times, once for each element in the structure array.

How Execution Grows With Input

As n grows, the number of field accesses grows directly with n.

Input Size (n)	Approx. Operations
10	10 field accesses
100	100 field accesses
1000	1000 field accesses

Pattern observation: The time grows in a straight line as the number of elements increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to access all fields grows directly in proportion to the number of elements.

Common Mistake

[X] Wrong: "Accessing a field in a structure is instant and does not depend on the number of elements."

[OK] Correct: While accessing one field is quick, doing it repeatedly for many elements adds up, so total time grows with the number of elements.

Interview Connect

Knowing how data access time grows helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we accessed multiple fields inside the loop instead of just one? How would the time complexity change?"