realloc function - Time & Space Complexity

Time Complexity: realloc function

O(n)

Understanding Time Complexity

When using the realloc function in C, it's important to understand how the time it takes grows as the size of the memory changes.

We want to know how the work done by realloc changes when we ask for bigger or smaller memory blocks.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int *arr = malloc(10 * sizeof(int));
// ... use arr ...
arr = realloc(arr, 20 * sizeof(int));
// ... use arr with new size ...
    

This code first allocates memory for 10 integers, then resizes it to hold 20 integers using realloc.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Copying existing data from old memory to new memory if needed.
• How many times: Number of elements copied depends on the old size of the memory block.

How Execution Grows With Input

When realloc needs to move data, it copies all existing elements to the new space.

Input Size (n)	Approx. Operations (copying elements)
10	10 copies
100	100 copies
1000	1000 copies

Pattern observation: The work grows directly with the number of elements already allocated.

Final Time Complexity

Time Complexity: O(n)

This means the time realloc takes grows linearly with the size of the existing memory block.

Common Mistake

[X] Wrong: "realloc always takes the same time no matter the size."

[OK] Correct: If realloc must move data, it copies all existing elements, so bigger blocks take more time.

Interview Connect

Understanding how memory resizing works helps you write efficient programs and answer questions about managing resources in real projects.

Self-Check

"What if realloc can expand the memory in place without copying? How would the time complexity change?"