Why structures are needed - Performance Analysis

Time Complexity: Why structures are needed

O(n)

Understanding Time Complexity

We want to understand how using structures affects the time it takes for a program to run.

How does grouping data together change the work the program does?

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 defines a structure to hold two numbers and prints each point from an array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each point in the array.
• How many times: Exactly once for each point, so n times.

How Execution Grows With Input

As the number of points grows, the program prints more lines, doing more work.

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

Pattern observation: The work grows directly with the number of points.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line with the number of points.

Common Mistake

[X] Wrong: "Using structures makes the program slower because it adds extra steps."

[OK] Correct: Structures group related data, but accessing them in a loop still takes time proportional to the number of items, not more.

Interview Connect

Understanding how data grouping affects program speed helps you write clear and efficient code, a skill valued in many coding challenges.

Self-Check

"What if we added another loop inside to print each coordinate separately? How would the time complexity change?"