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?"

Practice

1. What does the realloc function do in C programming?

easy

A. It allocates a new memory block without preserving old data.

B. It frees the allocated memory block immediately.

C. It changes the size of a previously allocated memory block, preserving its content.

D. It copies data from one memory block to another.

Solution

1. Step 1: Understand the purpose of realloc

   The realloc function is used to resize an existing memory block allocated by malloc or calloc.

2. Step 2: Check data preservation behavior

   realloc preserves the existing data up to the minimum of old and new sizes.

3. Final Answer:

   It changes the size of a previously allocated memory block, preserving its content. -> Option C

4. Quick Check:

   realloc resizes memory and keeps data [OK]

Hint: Remember: realloc resizes and keeps old data safe [OK]

Common Mistakes:

• Thinking realloc frees memory without resizing
• Assuming realloc always allocates new memory without preserving data
• Confusing realloc with memcpy or free

2. Which of the following is the correct syntax to resize a memory block pointed by ptr to hold 50 integers using realloc?

easy

A. ptr = realloc(ptr, 50 * sizeof(int));

B. ptr = realloc(sizeof(int), 50 * ptr);

C. ptr = realloc(50, ptr * sizeof(int));

D. ptr = realloc(ptr, 50);

Solution

1. Step 1: Understand realloc parameters

   realloc takes a pointer and the new size in bytes. To hold 50 integers, size must be 50 times size of int.

2. Step 2: Check each option's correctness

   ptr = realloc(ptr, 50 * sizeof(int)); correctly multiplies 50 by sizeof(int). Others misuse parameters or sizes.

3. Final Answer:

   ptr = realloc(ptr, 50 * sizeof(int)); -> Option A

4. Quick Check:

   Size in bytes = count * sizeof(type) [OK]

Hint: Multiply count by sizeof(type) for realloc size [OK]

Common Mistakes:

• Passing count instead of bytes as size
• Swapping parameters in realloc
• Forgetting sizeof(int) when resizing

3. What will be the output of this code snippet?

int *arr = malloc(3 * sizeof(int));
arr[0] = 1; arr[1] = 2; arr[2] = 3;
arr = realloc(arr, 5 * sizeof(int));
arr[3] = 4; arr[4] = 5;
for(int i = 0; i < 5; i++) printf("%d ", arr[i]);
free(arr);

medium

A. 1 2 3 0 0

B. 1 2 3 4 5

C. Garbage values after 3 elements

D. Runtime error due to invalid access

Solution

1. Step 1: Analyze memory allocation and initialization

   Initially, 3 integers allocated and set to 1, 2, 3. Then resized to hold 5 integers.

2. Step 2: Assign new values and print

   After realloc, elements 3 and 4 are assigned 4 and 5. Printing all 5 elements outputs 1 2 3 4 5.

3. Final Answer:

   1 2 3 4 5 -> Option B

4. Quick Check:

   realloc preserves old data and new elements assigned [OK]

Hint: realloc keeps old data; new elements must be assigned [OK]

Common Mistakes:

• Assuming new elements are zeroed automatically
• Expecting garbage values without assignment
• Thinking realloc frees old data immediately

4. Identify the error in this code snippet:

int *ptr = malloc(10 * sizeof(int));
ptr = realloc(ptr, 20 * sizeof(int));
if (ptr == NULL) {
    printf("Memory allocation failed\n");
    free(ptr);
}

medium

A. Calling free(ptr) after ptr is NULL does not free the original memory block.

B. Missing check for malloc failure before realloc.

C. Incorrect size calculation in realloc.

D. No error; code is correct.

Solution

1. Step 1: Understand realloc return and NULL check

   If realloc returns NULL, original pointer is lost if not saved separately, and ptr becomes NULL.

2. Step 2: Analyze free(ptr) after NULL assignment

   Calling free(ptr) after ptr is NULL does not free the original memory block, leading to memory leak.

3. Final Answer:

   Calling free(ptr) after ptr is NULL does not free the original memory block. -> Option A

4. Quick Check:

   Check realloc result before overwriting pointer [OK]

Hint: Save realloc result before overwriting pointer [OK]

Common Mistakes:

• Not checking realloc return before assignment
• Freeing NULL pointer thinking it frees old memory
• Ignoring malloc failure before realloc

5. You have a dynamic array of integers allocated with malloc. You want to safely double its size using realloc without losing data or causing memory leaks. Which approach is correct?

hard

A. ptr = malloc(2 * current_size); memcpy(ptr, old_ptr, current_size); free(old_ptr);

B. ptr = realloc(ptr, 2 * current_size); // directly assign realloc result

C. free(ptr); ptr = malloc(2 * current_size); // allocate new memory after freeing

D. int *temp = realloc(ptr, 2 * current_size); if (temp) ptr = temp; else handle error;

Solution

1. Step 1: Understand safe realloc usage

   Directly assigning realloc result to original pointer risks losing original memory if realloc fails.

2. Step 2: Use temporary pointer to check realloc success

   Assign realloc to temp pointer, check if not NULL, then update original pointer. Else handle error safely.

3. Final Answer:

   int *temp = realloc(ptr, 2 * current_size); if (temp) ptr = temp; else handle error; -> Option D

4. Quick Check:

   Use temp pointer to avoid memory leaks on realloc failure [OK]

Hint: Use temp pointer for realloc to avoid losing original memory [OK]

Common Mistakes:

• Overwriting pointer before checking realloc result
• Freeing pointer before realloc causing data loss
• Not handling realloc failure properly