Memory allocation flow - Time & Space Complexity

Time Complexity: Memory allocation flow

O(n)

Understanding Time Complexity

When a program asks for memory, it takes some time to find and give that space.

We want to see how the time to get memory grows as the program asks for more.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdlib.h>

int main() {
    int n = 1000;
    for (int i = 0; i < n; i++) {
        int* ptr = (int*)malloc(sizeof(int));
        if (ptr == NULL) return -1;
        // use ptr
        free(ptr);
    }
    return 0;
}
    

This code requests memory for one integer n times, then frees it each time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calling malloc and free inside a loop.
• How many times: Exactly n times, once per loop iteration.

How Execution Grows With Input

Each time the loop runs, the program asks for memory once and frees it once.

Input Size (n)	Approx. Operations
10	20 (10 malloc + 10 free)
100	200 (100 malloc + 100 free)
1000	2000 (1000 malloc + 1000 free)

Pattern observation: The number of operations grows directly with n; doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to allocate and free memory grows linearly as the number of requests increases.

Common Mistake

[X] Wrong: "Memory allocation is instant and does not affect performance."

[OK] Correct: Each malloc call takes time to find free space and manage memory, so many calls add up and slow the program.

Interview Connect

Understanding how memory allocation time grows helps you write efficient programs and answer questions about resource use in real projects.

Self-Check

"What if we allocated memory once outside the loop and reused it inside? How would the time complexity change?"