Nested interrupt handling in FreeRTOS - Time & Space Complexity

Time Complexity: Nested interrupt handling

O(n)

Understanding Time Complexity

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

We want to know how the total handling time changes when interrupts can interrupt other interrupts.

Scenario Under Consideration

Analyze the time complexity of the following nested interrupt handling code snippet.

void ISR1(void) {
    // Handle interrupt 1
    if (condition_for_ISR2) {
        ISR2(); // Nested interrupt call
    }
    // Finish ISR1
}

void ISR2(void) {
    // Handle interrupt 2
}
    

This code shows one interrupt service routine (ISR1) that may call another ISR (ISR2) inside it, representing nested interrupts.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the number of interrupts increases, the total time spent handling them grows roughly in proportion to how many interrupts occur and how often nested interrupts happen.

Input Size (n)	Approx. Operations
10 interrupts	About 10 ISR1 calls plus some ISR2 calls
100 interrupts	About 100 ISR1 calls plus more ISR2 calls
1000 interrupts	About 1000 ISR1 calls plus many ISR2 calls

Pattern observation: The total handling time grows roughly linearly with the number of interrupts and nested calls.

Final Time Complexity

Time Complexity: O(n)

This means the total time to handle interrupts grows in a straight line as the number of interrupts increases, including nested ones.

Common Mistake

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

[OK] Correct: Each nested interrupt adds some fixed extra time, but they do not multiply the total time exponentially because interrupts are handled one after another, not all at once.

Interview Connect

Understanding how nested interrupts affect execution time helps you design responsive systems and shows you can think about how code behaves under real conditions.

Self-Check

"What if ISR2 could also call ISR1 again? How would the time complexity change?"