Choosing the right heap scheme in FreeRTOS - Time & Space Complexity

Time Complexity: Choosing the right heap scheme

O(n)

Understanding Time Complexity

When using FreeRTOS, choosing the right heap scheme affects how fast memory allocation and freeing happen.

We want to know how the time to allocate or free memory changes as the program runs longer or uses more memory.

Scenario Under Consideration

Analyze the time complexity of this heap allocation function from FreeRTOS heap_4 scheme.

void *pvPortMalloc( size_t xWantedSize ) {
    BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
    size_t xBlockSize;

    // Traverse free list to find a block big enough
    for( pxPreviousBlock = &xStart, pxBlock = xStart.pxNextFreeBlock;
         pxBlock->xBlockSize < xWantedSize && pxBlock->pxNextFreeBlock != NULL;
         pxPreviousBlock = pxBlock, pxBlock = pxBlock->pxNextFreeBlock ) {
        // loop body empty
    }

    if( pxBlock != &xEnd ) {
        // Allocate memory from this block
    }
    return NULL;
}
    

This code searches a linked list of free memory blocks to find a block large enough to allocate.

Identify Repeating Operations

Look for loops or repeated steps in the code.

• Primary operation: Loop through the free memory blocks linked list.
• How many times: Up to the number of free blocks in the list.

How Execution Grows With Input

The time to find a block grows as the number of free blocks grows.

Input Size (number of free blocks)	Approx. Operations (block checks)
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

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

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Memory allocation always happens instantly regardless of heap size."

[OK] Correct: The allocator must search free blocks, so more blocks mean more time to find space.

Interview Connect

Understanding how heap schemes affect allocation time helps you explain trade-offs in embedded systems memory management.

Self-Check

What if the heap scheme used a balanced tree instead of a linked list? How would the time complexity change?