Task priority assignment in FreeRTOS - Time & Space Complexity

Time Complexity: Task priority assignment

O(1)

Understanding Time Complexity

When assigning priorities to tasks in FreeRTOS, it is important to understand how the time to assign or change priorities grows as the number of tasks increases.

We want to know how the system handles priority changes as more tasks are added.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void vSetTaskPriority(TaskHandle_t xTask, UBaseType_t uxNewPriority) {
    taskENTER_CRITICAL();
    if (uxNewPriority != uxTaskPriorityGet(xTask)) {
        vTaskPrioritySet(xTask, uxNewPriority);
        vTaskPriorityInherit(xTask);
    }
    taskEXIT_CRITICAL();
}

This code changes the priority of a given task if the new priority is different from the current one, protecting the operation with a critical section.

Identify Repeating Operations

• Primary operation: The function vTaskPrioritySet internally may traverse the ready task lists to move the task to the correct priority list.
• How many times: It depends on the number of priority levels and tasks in those lists, but typically it involves a constant number of steps per priority level.

How Execution Grows With Input

As the number of tasks increases, the time to update priority involves moving the task between lists, which depends on the number of priority levels, not directly on total tasks.

Input Size (number of tasks)	Approx. Operations
10	Few steps to update priority list
100	Still a few steps, mostly constant
1000	Same few steps, does not grow with tasks

Pattern observation: The time to assign priority stays mostly the same even as tasks increase.

Final Time Complexity

Time Complexity: O(1)

This means changing a task's priority takes about the same time no matter how many tasks exist.

Common Mistake

[X] Wrong: "Changing a task's priority takes longer as more tasks are added because it must check all tasks."

[OK] Correct: The system uses priority lists, so it only moves the task between lists without scanning all tasks.

Interview Connect

Understanding how task priority assignment scales helps you explain real-time system behavior clearly and confidently.

Self-Check

"What if the system had to reorder tasks within the same priority list when changing priority? How would the time complexity change?"