Producer-consumer pattern in FreeRTOS - Time & Space Complexity

Time Complexity: Producer-consumer pattern

O(n)

Understanding Time Complexity

We want to understand how the time cost changes when using the producer-consumer pattern in FreeRTOS.

Specifically, how the number of operations grows as more items are produced and consumed.

Scenario Under Consideration

Analyze the time complexity of the following FreeRTOS producer-consumer code snippet.

void producerTask(void *params) {
    for (;;) {
        int item = produceItem();
        xQueueSend(queue, &item, portMAX_DELAY);
    }
}

void consumerTask(void *params) {
    int item;
    for (;;) {
        xQueueReceive(queue, &item, portMAX_DELAY);
        consumeItem(item);
    }
}
    

This code shows two tasks: one produces items and sends them to a queue, the other receives and consumes them.

Identify Repeating Operations

Look at what repeats in the code.

• Primary operation: The producer repeatedly sends items to the queue, and the consumer repeatedly receives items from the queue.
• How many times: Each loop runs indefinitely, processing one item per iteration.

How Execution Grows With Input

As the number of items to produce and consume grows, the tasks run more iterations.

Input Size (n items)	Approx. Operations
10	About 10 sends and 10 receives
100	About 100 sends and 100 receives
1000	About 1000 sends and 1000 receives

Pattern observation: The total operations grow directly with the number of items; doubling items doubles operations.

Final Time Complexity

Time Complexity: O(n)

This means the time to process items grows in a straight line with the number of items produced and consumed.

Common Mistake

[X] Wrong: "The producer or consumer runs in constant time no matter how many items there are."

[OK] Correct: Each item requires a send or receive operation, so more items mean more work and more time.

Interview Connect

Understanding how tasks interact and how their work scales is a key skill in real-time systems programming.

Self-Check

"What if the queue size is limited and sometimes full? How would that affect the time complexity of the producer task?"