Time Complexity: Choosing priorities for real applications
O(n)
0
0
Choosing priorities for real applications in FreeRTOS - Time & Space Complexity
Understanding Time Complexity
When we assign priorities to tasks in FreeRTOS, it affects how often tasks run and how long they wait.
We want to understand how the time to complete tasks changes as we add more tasks with different priorities.
Scenario Under Consideration
Analyze the time complexity of scheduling tasks with different priorities.
// Create tasks with different priorities
xTaskCreate(task1, "Task1", 1000, NULL, 3, NULL);
xTaskCreate(task2, "Task2", 1000, NULL, 2, NULL);
xTaskCreate(task3, "Task3", 1000, NULL, 1, NULL);
// Start the scheduler
vTaskStartScheduler();
This code creates three tasks with different priorities and starts the scheduler to run the highest priority task ready to run.
Identify Repeating Operations
Look at what repeats during scheduling:
- Primary operation: The scheduler checks all ready tasks to find the highest priority one.
- How many times: This check happens every time a task finishes or blocks, so it repeats often.
How Execution Grows With Input
As the number of tasks (n) grows, the scheduler must check more tasks to find the highest priority ready one.
| Input Size (n) | Approx. Operations |
|---|---|
| 3 | 3 checks per scheduling decision |
| 10 | 10 checks per scheduling decision |
| 100 | 100 checks per scheduling decision |
Pattern observation: The number of checks grows directly with the number of tasks.
Final Time Complexity
Time Complexity: O(n)
This means the scheduler's work grows linearly as you add more tasks with different priorities.
Common Mistake
[X] Wrong: "Adding more tasks won't affect scheduling time because priorities decide order instantly."
[OK] Correct: The scheduler still checks all ready tasks to find the highest priority one, so more tasks mean more checks.
Interview Connect
Understanding how task priorities affect scheduling time helps you design responsive systems and shows you can think about performance in real applications.
Self-Check
"What if all tasks have the same priority? How would the time complexity of scheduling change?"