What is an RTOS in FreeRTOS - Complexity Analysis

Time Complexity: What is an RTOS

O(n)

Understanding Time Complexity

When working with an RTOS, it is important to understand how tasks and operations take time as the system runs.

We want to know how the time needed changes when more tasks or events happen.

Scenario Under Consideration

Analyze the time complexity of a simple FreeRTOS task scheduler loop.

    void vTaskScheduler(void) {
        for (;;) {
            for (int i = 0; i < numTasks; i++) {
                if (tasks[i].state == READY) {
                    runTask(tasks[i]);
                }
            }
        }
    }
    

This code runs an infinite loop checking each task to see if it is ready, then runs it.

Identify Repeating Operations

Look for loops or repeated actions that take time.

• Primary operation: The inner loop that checks each task's state.
• How many times: It runs once per scheduler cycle, checking all tasks (numTasks times).

How Execution Grows With Input

As the number of tasks increases, the scheduler checks more tasks each cycle.

Input Size (numTasks)	Approx. Operations per cycle
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The work grows directly with the number of tasks.

Final Time Complexity

Time Complexity: O(n)

This means the scheduler's work grows in a straight line as the number of tasks increases.

Common Mistake

[X] Wrong: "The scheduler runs in the same time no matter how many tasks there are."

[OK] Correct: The scheduler must check each task, so more tasks mean more checks and more time.

Interview Connect

Understanding how an RTOS scheduler scales with tasks helps you explain system responsiveness and efficiency clearly.

Self-Check

"What if the scheduler used a priority queue instead of checking all tasks? How would the time complexity change?"