Bit field structures in Embedded C - Time & Space Complexity

Time Complexity: Bit field structures

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run code with bit field structures changes as the input grows.

Specifically, we ask: how does using bit fields affect the number of steps the program takes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Flags {
  unsigned int flag1 : 1;
  unsigned int flag2 : 1;
  unsigned int flag3 : 1;
};

void setFlags(struct Flags *f, int n) {
  for (int i = 0; i < n; i++) {
    f->flag1 = 1;
    f->flag2 = 0;
    f->flag3 = 1;
  }
}
    

This code sets three bit flags repeatedly in a loop that runs n times.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Setting three bit fields inside the loop.
• How many times: The loop runs n times, so these three bit assignments happen n times.

How Execution Grows With Input

Each time the loop runs, it does the same three bit assignments.

Input Size (n)	Approx. Operations
10	30 (3 assignments x 10)
100	300 (3 assignments x 100)
1000	3000 (3 assignments x 1000)

Pattern observation: The number of operations grows directly with n, meaning if n doubles, operations double.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the code grows in a straight line as the input size increases.

Common Mistake

[X] Wrong: "Bit field operations are always constant time, so the loop doesn't affect time complexity."

[OK] Correct: While each bit assignment is quick, the loop repeats these assignments n times, so total time grows with n.

Interview Connect

Understanding how loops with bit field operations scale helps you explain performance clearly and shows you grasp how low-level data affects program speed.

Self-Check

"What if we added another nested loop inside that runs m times? How would the time complexity change?"