Memory pool (fixed-size block allocator) in Embedded C - Time & Space Complexity

Time Complexity: Memory pool (fixed-size block allocator)

O(1)

Understanding Time Complexity

We want to understand how the time to allocate or free memory changes as the number of blocks grows.

How does the allocator's speed behave when managing many fixed-size blocks?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Simple fixed-size block allocator
void* mem_alloc() {
    if (free_list == NULL) return NULL; // no free blocks
    void* block = free_list;           // take first free block
    free_list = *(void**)free_list;   // update free list head
    return block;
}

void mem_free(void* block) {
    *(void**)block = free_list;       // add block back to free list
    free_list = block;
}
    

This code manages a list of free memory blocks. Allocation takes the first free block, and freeing adds a block back to the list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Access and update a pointer to the head of the free list.
• How many times: Each allocation or free does this once, no loops or recursion involved.

How Execution Grows With Input

Each allocation or free operation does a fixed number of steps regardless of how many blocks exist.

Input Size (n)	Approx. Operations
10	2-3 pointer steps
100	2-3 pointer steps
1000	2-3 pointer steps

Pattern observation: The number of steps stays the same no matter how many blocks are managed.

Final Time Complexity

Time Complexity: O(1)

This means allocation and freeing take the same short time no matter how many blocks are in the pool.

Common Mistake

[X] Wrong: "Allocation time grows as more blocks are used because the list gets longer."

[OK] Correct: The allocator always takes the first free block directly, so it does not search through the list.

Interview Connect

Understanding fixed-time memory operations shows you can reason about efficient resource management, a key skill in embedded systems and performance-critical code.

Self-Check

"What if the allocator searched the free list to find a block of a certain size? How would the time complexity change?"