Struct packing and alignment in Embedded C - Time & Space Complexity

Time Complexity: Struct packing and alignment

O(n)

Understanding Time Complexity

When working with structs in embedded C, how the data is packed and aligned affects how fast the program runs.

We want to see how the program's speed changes as the struct size or layout changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Data {
  char a;
  int b;
  char c;
};

void process(struct Data *arr, int n) {
  for (int i = 0; i < n; i++) {
    arr[i].b += 1;
  }
}
    

This code loops through an array of structs and updates one field in each struct.

Identify Repeating Operations

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

How Execution Grows With Input

As the number of structs grows, the loop runs more times, so the work grows directly with n.

Input Size (n)	Approx. Operations
10	10 updates
100	100 updates
1000	1000 updates

Pattern observation: The work grows in a straight line as n increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows directly with the number of structs you process.

Common Mistake

[X] Wrong: "Changing struct packing will change how many times the loop runs."

[OK] Correct: The loop count depends only on n, not on how the struct fields are arranged or padded.

Interview Connect

Understanding how struct layout affects memory but not loop count helps you explain performance clearly and confidently.

Self-Check

"What if we added a nested loop inside process that compares each struct to every other struct? How would the time complexity change?"