FreeRTOS heap implementations (heap_1 to heap_5) - Time & Space Complexity

Time Complexity: FreeRTOS heap implementations (heap_1 to heap_5)

O(n)

Understanding Time Complexity

When using FreeRTOS, memory allocation speed affects how fast tasks start and run. Different heap implementations manage memory differently, so their speed changes as memory requests grow.

We want to know how the time to allocate or free memory changes when the number of allocations increases.

Scenario Under Consideration

Analyze the time complexity of the heap_4 memory allocation function.

void *pvPortMalloc( size_t xSize ) {
    BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
    void *pvReturn = NULL;

    if( xSize > 0 ) {
        // Traverse free list to find a block big enough
        pxPreviousBlock = &xStart;
        pxBlock = xStart.pxNextFreeBlock;
        while( pxBlock != NULL && pxBlock->xBlockSize < xSize ) {
            pxPreviousBlock = pxBlock;
            pxBlock = pxBlock->pxNextFreeBlock;
        }
        // If found, allocate and adjust free list
        if( pxBlock != NULL && pxBlock->xBlockSize >= xSize ) {
            pvReturn = (void *)( ( uint8_t * ) pxBlock + heapSTRUCT_SIZE );
            // Adjust free list here
        }
    }
    return pvReturn;
}

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the number of free blocks grows, the search takes longer because it checks each block until it finds a fit.

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 in the heap.

Common Mistake

[X] Wrong: "Memory allocation always takes constant time regardless of heap size."

[OK] Correct: In FreeRTOS heap implementations like heap_4, allocation searches through free blocks, so more blocks mean more time.

Interview Connect

Understanding how memory allocation time grows helps you explain system responsiveness and resource management in embedded systems.

Self-Check

"What if the free blocks were kept in a sorted tree instead of a linked list? How would the time complexity change?"