Timer interrupt for periodic tasks in Embedded C - Time & Space Complexity

Time Complexity: Timer interrupt for periodic tasks

O(n)

Understanding Time Complexity

When using a timer interrupt to run tasks regularly, it is important to understand how the time taken grows as the task or timer settings change.

We want to know how the program's work changes when the timer triggers more often or the task does more work.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

volatile int flag = 0;

void Timer_ISR(void) {
    flag = 1;  // Set flag when timer interrupt occurs
}

int main() {
    while(1) {
        if(flag) {
            flag = 0;
            perform_task();  // Task to run periodically
        }
    }
}
    

This code uses a timer interrupt to set a flag. The main loop checks the flag and runs a task periodically when the flag is set.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The main loop runs continuously, checking the flag.
• How many times: The loop runs forever, but the task runs only when the flag is set by the timer interrupt.

How Execution Grows With Input

As the timer triggers more often, the task runs more times, increasing total work.

Input Size (Timer Triggers)	Approx. Operations (Task Runs)
10	10
100	100
1000	1000

Pattern observation: The total work grows directly with how many times the timer interrupt fires and the task runs.

Final Time Complexity

Time Complexity: O(n)

This means the total work grows linearly with the number of timer interrupts and task executions.

Common Mistake

[X] Wrong: "The main loop only runs once per timer interrupt because the flag controls it."

[OK] Correct: The main loop runs continuously, checking the flag many times even when the task does not run. The task runs only when the flag is set, but the loop itself is always active.

Interview Connect

Understanding how timer interrupts affect program work helps you design efficient embedded systems that respond well without wasting CPU time.

Self-Check

"What if the task inside the interrupt service routine instead of the main loop? How would the time complexity change?"