Nested structures - Time & Space Complexity

Time Complexity: Nested structures

O(n)

Understanding Time Complexity

When working with nested structures in C, it's important to see how the program's work grows as the data size grows.

We want to know how the time to process nested structures changes when the input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Point {
    int x;
    int y;
};

struct Rectangle {
    struct Point corners[4];
};

void printRectangles(struct Rectangle rects[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 4; j++) {
            printf("(%d, %d) ", rects[i].corners[j].x, rects[i].corners[j].y);
        }
        printf("\n");
    }
}

This code prints the coordinates of each corner of multiple rectangles stored in an array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop prints 4 corners for each rectangle.
• How many times: The outer loop runs n times, and for each, the inner loop runs 4 times.

How Execution Grows With Input

As the number of rectangles (n) grows, the total prints grow proportionally because each rectangle always has 4 corners.

Input Size (n)	Approx. Operations
10	40 (10 x 4)
100	400 (100 x 4)
1000	4000 (1000 x 4)

Pattern observation: The total work grows directly with n, since the inner loop count is fixed.

Final Time Complexity

Time Complexity: O(n)

This means the time to print all rectangles grows in a straight line as the number of rectangles 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 4 times, not depending on n, so it does not multiply n by n.

Interview Connect

Understanding how nested structures affect time helps you explain your code clearly and shows you can think about efficiency in real projects.

Self-Check

"What if the number of corners in each rectangle was not fixed at 4 but depended on input size m? How would the time complexity change?"