Memory usage monitoring in FreeRTOS - Time & Space Complexity

Time Complexity: Memory usage monitoring

O(n)

Understanding Time Complexity

When monitoring memory usage in FreeRTOS, it is important to understand how the time to check memory changes as the system runs.

We want to know how the cost of checking memory grows as the amount of memory or tasks increases.

Scenario Under Consideration

Analyze the time complexity of the following FreeRTOS memory check function.

size_t xPortGetFreeHeapSize(void) {
    size_t freeHeap = 0;
    for (BlockLink_t *pxBlock = pxStart; pxBlock != NULL; pxBlock = pxBlock->pxNextFreeBlock) {
        freeHeap += pxBlock->xBlockSize;
    }
    return freeHeap;
}
    

This function sums the sizes of all free memory blocks to find total free heap size.

Identify Repeating Operations

• Primary operation: Loop through each free memory block linked list node.
• How many times: Once for every free block in the heap.

How Execution Grows With Input

As the number of free memory blocks increases, the time to sum their sizes grows proportionally.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: The time grows linearly as the number of free blocks increases.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Checking free memory is always a quick constant-time operation."

[OK] Correct: The function must visit each free block, so time depends on how many blocks exist, not fixed.

Interview Connect

Understanding how memory monitoring scales helps you design efficient embedded systems and shows you can reason about resource costs clearly.

Self-Check

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