Watchdog task pattern in FreeRTOS - Time & Space Complexity

Time Complexity: Watchdog task pattern

O(n)

Understanding Time Complexity

We want to understand how the time cost changes when running a watchdog task in FreeRTOS.

Specifically, how the task checks other tasks and how this scales as more tasks are added.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void WatchdogTask(void *pvParameters) {
    for (;;) {
        for (int i = 0; i < numTasks; i++) {
            if (!IsTaskResponsive(i)) {
                HandleUnresponsiveTask(i);
            }
        }
        vTaskDelay(WATCHDOG_DELAY);
    }
}
    

This code runs forever, checking each task once per cycle to see if it is responsive.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner for-loop that checks each task's responsiveness.
• How many times: It runs once every watchdog cycle, iterating over all tasks (numTasks times).

How Execution Grows With Input

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

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to complete one watchdog cycle grows linearly as the number of tasks increases.

Common Mistake

[X] Wrong: "The watchdog task runs in constant time no matter how many tasks there are."

[OK] Correct: Because the watchdog checks each task one by one, more tasks mean more checks, so time grows with the number of tasks.

Interview Connect

Understanding how a watchdog task scales helps you design reliable systems and shows you can reason about task monitoring in real-time software.

Self-Check

"What if the watchdog only checked a fixed number of tasks each cycle instead of all tasks? How would the time complexity change?"