Nested structures in C++ - Time & Space Complexity

Time Complexity: Nested structures

O(n)

Understanding Time Complexity

When we use nested structures in code, it often means some parts repeat inside others.

We want to see how the total work grows as the input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Inner {
    int value;
};

struct Outer {
    Inner arr[5];
};

void process(Outer data[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 5; j++) {
            data[i].arr[j].value += 1;
        }
    }
}
    

This code loops through an array of Outer structures, each containing an array of Inner structures, and updates a value inside each Inner.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop updates each Inner element's value.
• How many times: The outer loop runs n times, and for each, the inner loop runs 5 times.

How Execution Grows With Input

As n grows, the total updates grow proportionally to n times 5.

Input Size (n)	Approx. Operations
10	10 x 5 = 50
100	100 x 5 = 500
1000	1000 x 5 = 5000

Pattern observation: The total work grows directly with n, multiplied by a fixed number 5.

Final Time Complexity

Time Complexity: O(n)

This means the work grows in a straight line as the input size increases.

Common Mistake

[X] Wrong: "Because there are two loops, the time complexity must be quadratic O(n²)."

[OK] Correct: The inner loop runs a fixed 5 times, not depending on n, so it does not multiply n by itself.

Interview Connect

Understanding how nested structures affect time helps you explain code efficiency clearly and confidently.

Self-Check

"What if the inner array size changed from 5 to n? How would the time complexity change?"