Array of structures - Time & Space Complexity

Time Complexity: Array of structures

O(n)

Understanding Time Complexity

When working with an array of structures, it's important to know how the time to process them grows as the array gets bigger.

We want to understand how the number of operations changes when we access or loop through these structures.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Point {
    int x;
    int y;
};

void printPoints(struct Point points[], int n) {
    for (int i = 0; i < n; i++) {
        printf("(%d, %d)\n", points[i].x, points[i].y);
    }
}
    

This code loops through an array of Point structures and prints each point's coordinates.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing and printing each structure in the array.
• How many times: Exactly once for each element, so n times.

How Execution Grows With Input

As the number of points increases, the total work grows directly with it.

Input Size (n)	Approx. Operations
10	10 print operations
100	100 print operations
1000	1000 print operations

Pattern observation: Doubling the number of points doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to process the array grows in a straight line with the number of elements.

Common Mistake

[X] Wrong: "Accessing a structure inside an array is slower and adds extra loops."

[OK] Correct: Accessing each structure is done directly by index in one loop, so it does not add extra loops or slow down beyond the main loop.

Interview Connect

Understanding how looping through arrays of structures scales helps you explain and write efficient code when handling collections of data in real projects.

Self-Check

"What if we nested another loop inside to compare each point with every other point? How would the time complexity change?"