Defining structures - Time & Space Complexity

Time Complexity: Defining structures

O(n)

Understanding Time Complexity

When we define structures in C, we want to know how this affects the time it takes to create and use them.

We ask: How does the program's work grow when we use structures?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Point {
    int x;
    int y;
};

void initializePoints(struct Point points[], int n) {
    for (int i = 0; i < n; i++) {
        points[i].x = i;
        points[i].y = i * 2;
    }
}
    

This code defines a structure and initializes an array of these structures with values.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that sets values for each structure in the array.
• How many times: It runs once for each element, so n times.

How Execution Grows With Input

As the number of points (n) grows, the work grows in a straight line with it.

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

Pattern observation: Doubling the input roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to initialize grows directly with the number of points.

Common Mistake

[X] Wrong: "Defining a structure makes the program slower in a way that depends on the structure size."

[OK] Correct: Defining a structure itself does not add repeated work; only using it in loops affects time based on how many times you run those loops.

Interview Connect

Understanding how structures and loops work together helps you explain how programs handle data efficiently, a key skill in many coding tasks.

Self-Check

"What if we added a nested loop inside initializePoints to set more values? How would the time complexity change?"