NVIC (Nested Vectored Interrupt Controller) in ARM Architecture - Time & Space Complexity

Time Complexity: NVIC (Nested Vectored Interrupt Controller)

O(n)

Understanding Time Complexity

When working with the NVIC, it is important to understand how interrupt handling time grows as the number of interrupts increases.

We want to know how the time to process interrupts changes when more interrupts are enabled or pending.

Scenario Under Consideration

Analyze the time complexity of checking and servicing interrupts in NVIC.

// Simplified NVIC interrupt handling loop
while (1) {
  for (int i = 0; i < NUM_INTERRUPTS; i++) {
    if (NVIC->ISPR[i / 32] & (1 << (i % 32))) {
      NVIC->ICPR[i / 32] = (1 << (i % 32)); // Clear pending
      handle_interrupt(i); // Service interrupt
    }
  }
}
    

This code checks each possible interrupt line to see if it is pending, clears it, and then handles it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through all interrupt lines to check pending status.
• How many times: Once per main loop iteration, checking each interrupt line.

How Execution Grows With Input

As the number of interrupts (n) increases, the time to check all lines grows proportionally.

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

Pattern observation: The number of checks grows linearly with the number of interrupts.

Final Time Complexity

Time Complexity: O(n)

This means the time to check and handle interrupts grows directly in proportion to the number of interrupt lines.

Common Mistake

[X] Wrong: "Checking interrupts happens instantly regardless of how many interrupts exist."

[OK] Correct: Each interrupt line must be checked, so more interrupts mean more work and longer checking time.

Interview Connect

Understanding how interrupt checking scales helps you reason about system responsiveness and efficiency in embedded systems.

Self-Check

"What if the NVIC used a hardware priority encoder to find the highest priority pending interrupt instead of checking all lines? How would the time complexity change?"