xTaskNotifyGive() as lightweight semaphore in FreeRTOS - Time & Space Complexity

Time Complexity: xTaskNotifyGive() as lightweight semaphore

O(n)

Understanding Time Complexity

We want to understand how the time cost changes when using xTaskNotifyGive() as a lightweight semaphore in FreeRTOS.

Specifically, how does the number of operations grow when tasks notify each other?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void Task1(void *pvParameters) {
    for (;;) {
        // Do some work
        xTaskNotifyGive(Task2Handle);  // Notify Task2
        vTaskDelay(pdMS_TO_TICKS(100));
    }
}

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

This code shows one task notifying another using xTaskNotifyGive() as a lightweight semaphore to signal events.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The notification send and receive calls inside infinite loops.
• How many times: Each task loops forever, sending or waiting for notifications repeatedly.

How Execution Grows With Input

Each notification operation happens once per loop cycle, independent of any input size.

Input Size (n)	Approx. Operations
10	10 notifications sent and received
100	100 notifications sent and received
1000	1000 notifications sent and received

Pattern observation: The number of operations grows linearly with the number of notification events, but each event is a simple, constant-time operation.

Final Time Complexity

Time Complexity: O(n)

This means the total time grows linearly with the number of notifications, but each notification send or receive takes a constant amount of time.

Common Mistake

[X] Wrong: "Using xTaskNotifyGive() causes time to grow with the number of notifications queued."

[OK] Correct: Notifications do not queue up like messages; each call is a simple flag set or clear, so the time per call stays constant.

Interview Connect

Understanding how lightweight synchronization like xTaskNotifyGive() works helps you write efficient multitasking code and shows you know how to reason about task communication costs.

Self-Check

"What if we replaced xTaskNotifyGive() with a queue send operation? How would the time complexity change?"