Deferred interrupt processing architecture in FreeRTOS - Time & Space Complexity

Time Complexity: Deferred interrupt processing architecture

O(n)

Understanding Time Complexity

When using deferred interrupt processing, we want to know how the time to handle interrupts changes as more interrupts happen.

We ask: How does the system's work grow when more interrupts are deferred for later processing?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Interrupt Service Routine (ISR)
void ISR_Handler() {
    BaseType_t xHigherPriorityTaskWoken = pdFALSE;
    xQueueSendFromISR(deferredQueue, &data, &xHigherPriorityTaskWoken);
    portYIELD_FROM_ISR(xHigherPriorityTaskWoken);
}

// Deferred processing task
void DeferredTask(void *params) {
    DataType data;
    while(1) {
        if(xQueueReceive(deferredQueue, &data, portMAX_DELAY) == pdPASS) {
            ProcessData(data);
        }
    }
}
    

This code defers work from the interrupt to a task by sending data to a queue, then the task processes each item.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The deferred task loops forever, receiving and processing each queued item one by one.
• How many times: Once per deferred interrupt event, so as many times as interrupts occur.

How Execution Grows With Input

Each interrupt adds one item to the queue, and the task processes each item individually.

Input Size (n)	Approx. Operations
10	10 processing calls
100	100 processing calls
1000	1000 processing calls

Pattern observation: The work grows directly with the number of interrupts deferred.

Final Time Complexity

Time Complexity: O(n)

This means the total processing time grows linearly with the number of deferred interrupts.

Common Mistake

[X] Wrong: "Deferring work means the interrupt handling time is always constant no matter how many interrupts happen."

[OK] Correct: While the interrupt itself is quick, the deferred task must still process each item, so total work grows with the number of interrupts.

Interview Connect

Understanding how deferred interrupt processing scales helps you design responsive systems and shows you can think about how code behaves as load increases.

Self-Check

"What if the deferred task processed multiple items at once instead of one by one? How would the time complexity change?"