pvPortMalloc and vPortFree in FreeRTOS - Time & Space Complexity

Time Complexity: pvPortMalloc and vPortFree

O(n)

Understanding Time Complexity

When using pvPortMalloc and vPortFree in FreeRTOS, it's important to understand how the time to allocate and free memory changes as the program runs.

We want to know how the cost of these operations grows when the system manages more memory blocks.

Scenario Under Consideration

Analyze the time complexity of the following FreeRTOS memory allocation and freeing code.

void *ptr = pvPortMalloc(size);
if(ptr != NULL) {
    // Use the allocated memory
    vPortFree(ptr);
}
    

This code allocates a block of memory of given size and then frees it after use.

Identify Repeating Operations

Look for loops or repeated steps inside the allocation and free functions.

• Primary operation: Searching through the free memory blocks to find a suitable block for allocation or to merge freed blocks.
• How many times: The search may check multiple blocks depending on how fragmented the memory is.

How Execution Grows With Input

As the number of free memory blocks increases, the time to find a suitable block or merge blocks grows.

Input Size (number of free blocks)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The number of operations grows roughly in direct proportion to the number of free blocks.

Final Time Complexity

Time Complexity: O(n)

This means the time to allocate or free memory grows linearly with the number of free memory blocks.

Common Mistake

[X] Wrong: "Memory allocation and freeing always take the same fixed time no matter what."

[OK] Correct: The time depends on how many free blocks exist and how fragmented the memory is, so it can take longer if there are many blocks to check.

Interview Connect

Understanding how memory allocation time grows helps you reason about system performance and resource management in embedded systems.

Self-Check

"What if the memory allocator used a different data structure like a balanced tree? How would the time complexity change?"