Nested interrupts in Embedded C - Time & Space Complexity

Time Complexity: Nested interrupts

O(n)

Understanding Time Complexity

When using nested interrupts, it's important to understand how the time spent handling interrupts grows as more interrupts occur.

We want to see how the total work changes when interrupts can interrupt other interrupts.

Scenario Under Consideration

Analyze the time complexity of this embedded C code with nested interrupts.

volatile int count = 0;

void ISR1() {
  count++;
  if (interrupt2_pending()) {
    ISR2();  // Nested interrupt call
  }
}

void ISR2() {
  count += 2;
}
    

This code increments a counter in ISR1 and may call ISR2 inside it if another interrupt is pending.

Identify Repeating Operations

Look for repeated actions that take time.

• Primary operation: ISR1 runs and may call ISR2 inside it.
• How many times: ISR1 runs once per interrupt, ISR2 runs only if another interrupt is pending during ISR1.

How Execution Grows With Input

Imagine the number of interrupts as input size n.

Input Size (n)	Approx. Operations
10	About 10 calls to ISR1, some with ISR2 nested
100	About 100 calls to ISR1, more nested ISR2 calls
1000	About 1000 calls to ISR1, many nested ISR2 calls

As interrupts increase, total work grows roughly proportional to the number of interrupts and how often nesting happens.

Final Time Complexity

Time Complexity: O(n)

This means the total time grows linearly with the number of interrupts, even with nesting.

Common Mistake

[X] Wrong: "Nested interrupts multiply the time exponentially."

[OK] Correct: Each interrupt still runs once per event; nesting adds some extra calls but does not multiply work exponentially.

Interview Connect

Understanding how nested interrupts affect execution time helps you reason about real embedded systems and write efficient interrupt handlers.

Self-Check

"What if ISR2 could also trigger ISR1 again? How would that affect the time complexity?"