LED control patterns in Embedded C - Time & Space Complexity

Time Complexity: LED control patterns

O(n)

Understanding Time Complexity

When controlling LEDs in patterns, it is important to know how the time taken grows as the number of LEDs or steps increases.

We want to find out how the program's running time changes when we change the pattern size.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void led_pattern(int n) {
    for (int i = 0; i < n; i++) {
        turn_on_led(i);
        delay(100);
        turn_off_led(i);
    }
}
    

This code turns on each LED one by one, waits a bit, then turns it off, repeating for n LEDs.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that turns on and off each LED.
• How many times: It runs exactly n times, once for each LED.

How Execution Grows With Input

As the number of LEDs (n) increases, the total time grows directly with n.

Input Size (n)	Approx. Operations
10	About 10 on-off cycles
100	About 100 on-off cycles
1000	About 1000 on-off cycles

Pattern observation: Doubling the number of LEDs doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time grows in a straight line with the number of LEDs controlled.

Common Mistake

[X] Wrong: "The delay inside the loop makes the time complexity exponential."

[OK] Correct: The delay adds a fixed wait each loop, so total time still grows linearly with n, not exponentially.

Interview Connect

Understanding how loops affect time helps you explain how embedded systems handle tasks efficiently.

Self-Check

"What if we nested another loop inside to blink each LED multiple times? How would the time complexity change?"