Critical sections and interrupt disabling in FreeRTOS - Time & Space Complexity

Time Complexity: Critical sections and interrupt disabling

O(n)

Understanding Time Complexity

When using critical sections and disabling interrupts in FreeRTOS, it's important to know how the time spent changes as the code inside grows.

We want to see how the execution time grows when protecting code with interrupts disabled.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void exampleFunction(int n) {
    taskENTER_CRITICAL();  // Disable interrupts
    for (int i = 0; i < n; i++) {
        // Critical work here
        doSomeWork(i);
    }
    taskEXIT_CRITICAL();   // Enable interrupts
}
    

This code disables interrupts, runs a loop n times doing some work, then enables interrupts again.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop running doSomeWork() n times inside the critical section.
• How many times: Exactly n times, where n is the input size.

How Execution Grows With Input

As n grows, the time spent with interrupts disabled grows directly with n because the loop runs n times inside the critical section.

Input Size (n)	Approx. Operations
10	10 times doSomeWork()
100	100 times doSomeWork()
1000	1000 times doSomeWork()

Pattern observation: The time grows linearly as n increases.

Final Time Complexity

Time Complexity: O(n)

This means the time spent with interrupts disabled grows directly in proportion to the size of the work inside the critical section.

Common Mistake

[X] Wrong: "Disabling interrupts only takes a fixed small time, so the whole function always runs fast regardless of n."

[OK] Correct: The disabling is quick, but the loop inside runs n times while interrupts are off, so the total time with interrupts disabled grows with n.

Interview Connect

Understanding how critical sections affect timing helps you write responsive embedded code and shows you can reason about how code changes impact system behavior.

Self-Check

"What if the loop was moved outside the critical section, only disabling interrupts briefly inside the loop? How would the time complexity of the critical section change?"