ISR-to-task notification pattern in FreeRTOS - Time & Space Complexity

Time Complexity: ISR-to-task notification pattern

O(n)

Understanding Time Complexity

We want to understand how the time cost changes when an interrupt signals a task using notifications.

How does the number of notifications affect the time taken by the system?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void ISR_Handler(void) {
    BaseType_t xHigherPriorityTaskWoken = pdFALSE;
    vTaskNotifyGiveFromISR(TaskHandle, &xHigherPriorityTaskWoken);
    portYIELD_FROM_ISR(xHigherPriorityTaskWoken);
}

void TaskFunction(void *pvParameters) {
    for (;;) {
        ulTaskNotifyTake(pdTRUE, portMAX_DELAY);
        // Process notification
    }
}

This code shows an interrupt service routine sending notifications to a task, which waits and processes them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The task waits in a loop for notifications and processes each one.
• How many times: The loop runs once per notification received, repeating indefinitely.

How Execution Grows With Input

Each notification triggers one loop iteration in the task to process it.

Input Size (notifications)	Approx. Operations
10	10 task loop iterations
100	100 task loop iterations
1000	1000 task loop iterations

Pattern observation: The number of operations grows directly with the number of notifications.

Final Time Complexity

Time Complexity: O(n)

This means the time to process notifications grows linearly with how many notifications arrive.

Common Mistake

[X] Wrong: "The task processes all notifications instantly, so time does not grow with more notifications."

[OK] Correct: Each notification causes the task to run once, so more notifications mean more processing time.

Interview Connect

Understanding how tasks handle notifications from interrupts helps you explain real-time system responsiveness and workload management clearly.

Self-Check

"What if the task processes multiple notifications in one loop iteration? How would the time complexity change?"