Common embedded bugs and fixes in Embedded C - Time & Space Complexity

Time Complexity: Common embedded bugs and fixes

O(n)

Understanding Time Complexity

When we look at common bugs in embedded C code, we want to understand how the time it takes to run the code changes as inputs or conditions change.

We ask: How do these bugs affect the speed or efficiency of the program?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void delay(int count) {
    while(count-- > 0) {
        // empty loop for delay
    }
}

void process_data(int *data, int size) {
    for(int i = 0; i < size; i++) {  // bug fixed: changed <= to < to avoid off-by-one error
        data[i] = data[i] * 2;
    }
}
    

This code has a delay loop and a function that processes an array. The original off-by-one bug has been fixed to prevent unexpected behavior.

Identify Repeating Operations

Look at the loops that repeat operations.

• Primary operation: The for-loop in process_data that multiplies each array element.
• How many times: It runs size times, correctly processing each element once.

How Execution Grows With Input

The loop runs exactly as many times as the size of the input array, ensuring no extra work or errors.

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

Pattern observation: The loop runs exactly the intended number of times, preventing out-of-bounds access.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows directly with the size of the input array, with no extra cost or errors.

Common Mistake

[X] Wrong: "The loop runs exactly the number of elements in the array without error."

[OK] Correct: Because the loop condition originally used <= instead of <, it ran one extra time, causing out-of-bounds access and possible crashes.

Interview Connect

Understanding how small bugs affect time and behavior shows your attention to detail and helps you write safer, more efficient embedded code.

Self-Check

"What if we changed the loop condition from <= size to < size? How would the time complexity and safety change?"