Trace hooks and FreeRTOS+Trace - Time & Space Complexity

Time Complexity: Trace hooks and FreeRTOS+Trace

O(n)

Understanding Time Complexity

When using trace hooks and FreeRTOS+Trace, we want to know how adding tracing affects the program's speed.

We ask: How does tracing change the time the system takes as tasks run?

Scenario Under Consideration

Analyze the time complexity of the following trace hook code snippet.

void traceTASK_SWITCHED_IN(void) {
    // Called every time a task starts running
    recordTaskSwitchIn(xTaskGetCurrentTaskHandle());
}

void recordTaskSwitchIn(TaskHandle_t task) {
    // Log task switch event
    traceBuffer[traceIndex++] = task;
}
    

This code logs each task switch by recording the current task handle into a buffer.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recording a task switch event into a buffer.
• How many times: Once every time the scheduler switches tasks.

How Execution Grows With Input

Each task switch adds one operation to record the event.

Input Size (n)	Approx. Operations
10 task switches	10 record operations
100 task switches	100 record operations
1000 task switches	1000 record operations

Pattern observation: The number of operations grows directly with the number of task switches.

Final Time Complexity

Time Complexity: O(n)

This means the time spent tracing grows linearly with how many task switches happen.

Common Mistake

[X] Wrong: "Trace hooks run once and do not affect performance much."

[OK] Correct: Trace hooks run every task switch, so their cost adds up as switches increase.

Interview Connect

Understanding how tracing affects time helps you explain performance trade-offs in real-time systems clearly and confidently.

Self-Check

"What if the trace hook also logged extra data with each switch? How would the time complexity change?"