Tick timer and scheduler in FreeRTOS - Time & Space Complexity

Time Complexity: Tick timer and scheduler

O(n)

Understanding Time Complexity

We want to understand how the time it takes for the tick timer and scheduler to run changes as the system workload grows.

Specifically, how does the scheduler's work increase when more tasks are ready to run?

Scenario Under Consideration

Analyze the time complexity of the following FreeRTOS tick handler and scheduler call.

void vApplicationTickHook(void) {
    // Called every tick interrupt
    if (xSchedulerRunning) {
        if (xTaskIncrementTick() != pdFALSE) {
            vTaskSwitchContext();
        }
    }
}
    

This code runs on every tick interrupt. It updates the system tick count and switches tasks if needed.

Identify Repeating Operations

Look for loops or repeated work inside the scheduler call.

• Primary operation: The scheduler checks all ready tasks to find the highest priority one.
• How many times: It examines each ready task once per tick.

How Execution Grows With Input

As the number of ready tasks increases, the scheduler must check more tasks each tick.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

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

Final Time Complexity

Time Complexity: O(n)

This means the scheduler's work grows linearly as more tasks are ready to run.

Common Mistake

[X] Wrong: "The scheduler always runs in constant time regardless of tasks."

[OK] Correct: The scheduler must check each ready task to pick the next one, so more tasks mean more work.

Interview Connect

Understanding how scheduler time grows helps you design efficient multitasking systems and shows you can reason about system performance.

Self-Check

"What if the scheduler used a priority queue to track ready tasks? How would the time complexity change?"