Stack size allocation in FreeRTOS - Time & Space Complexity

Time Complexity: Stack size allocation

O(n)

Understanding Time Complexity

When we allocate stack size in FreeRTOS tasks, we want to know how the time to allocate grows as the stack size changes.

We ask: How does increasing the stack size affect the time the system spends setting it up?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Create a task with a given stack size
xTaskCreate(
  TaskFunction,       // Task function
  "TaskName",        // Name
  stackSize,          // Stack size in words
  NULL,               // Parameters
  tskIDLE_PRIORITY,   // Priority
  NULL                // Task handle
);
    

This code creates a FreeRTOS task and allocates memory for its stack based on stackSize.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Allocating and initializing the stack memory of size stackSize.
• How many times: The system sets up each stack element once during allocation.

How Execution Grows With Input

As the stack size increases, the system spends more time setting up the stack memory.

Input Size (stackSize)	Approx. Operations
10	10 operations (setting up each stack word)
100	100 operations
1000	1000 operations

Pattern observation: The time grows directly with the stack size; doubling the stack size roughly doubles the setup time.

Final Time Complexity

Time Complexity: O(n)

This means the time to allocate and initialize the stack grows linearly with the stack size.

Common Mistake

[X] Wrong: "Allocating a larger stack size takes the same time as a smaller one because it's just one call."

[OK] Correct: Even though it's one function call, the system must set up each stack element, so bigger stacks take more time.

Interview Connect

Understanding how stack size affects allocation time helps you reason about resource use in embedded systems, a key skill for real-world programming.

Self-Check

"What if the stack memory was allocated from a pre-allocated pool instead of dynamically? How would the time complexity change?"