free function - Time & Space Complexity

Time Complexity: free function

O(1)

Understanding Time Complexity

Let's see how the time cost changes when we use the free function in C.

We want to know how long it takes to release memory as the size of the data grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int *arr = malloc(n * sizeof(int));
// ... use the array ...
free(arr);
    

This code allocates memory for an array of integers and then frees it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The free function releases the allocated memory block.
• How many times: It is called once, regardless of the size of the memory block.

How Execution Grows With Input

Freeing memory takes about the same time no matter how big the block is.

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

Pattern observation: The time to free memory stays roughly the same even if the size grows.

Final Time Complexity

Time Complexity: O(1)

This means freeing memory takes a constant amount of time no matter how big the memory block is.

Common Mistake

[X] Wrong: "Freeing a large block of memory takes longer than a small one."

[OK] Correct: The free function just marks the memory as available; it does not clear or process each byte, so the time does not grow with size.

Interview Connect

Understanding how memory management functions like free work helps you write efficient programs and answer questions about resource handling clearly.

Self-Check

"What if we replaced free with a function that zeroes out the memory before freeing? How would the time complexity change?"

Practice

1. What is the main purpose of the free function in C?

easy

A. To initialize a pointer to NULL

B. To allocate new memory dynamically

C. To copy data from one memory location to another

D. To release memory previously allocated by malloc or similar functions

Solution

1. Step 1: Understand what free does

   The free function releases memory that was allocated dynamically, returning it to the system.

2. Step 2: Differentiate from other memory functions

   malloc allocates memory, free releases it. Copying or initializing pointers is unrelated.

3. Final Answer:

   To release memory previously allocated by malloc or similar functions -> Option D

4. Quick Check:

   free releases memory = A [OK]

Hint: Remember: free returns memory, malloc gets memory [OK]

Common Mistakes:

• Confusing free with malloc or calloc
• Thinking free allocates memory
• Using free to copy data

2. Which of the following is the correct way to free memory allocated by malloc?

easy

A. free(pointer); pointer = NULL;

B. free(pointer); free(pointer);

C. free(pointer); pointer++;

D. free(pointer); pointer = malloc(10);

Solution

1. Step 1: Free the allocated memory

   Calling free(pointer); releases the memory correctly.

2. Step 2: Avoid dangling pointer

   Setting pointer = NULL; after freeing prevents accidental use of freed memory.

3. Final Answer:

   free(pointer); pointer = NULL; -> Option A

4. Quick Check:

   Free then NULL pointer = D [OK]

Hint: Always set pointer to NULL after free to avoid bugs [OK]

Common Mistakes:

• Calling free twice on the same pointer
• Incrementing pointer after free
• Reassigning pointer without freeing first

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

char *ptr = malloc(5);
strcpy(ptr, "test");
free(ptr);
printf("%s", ptr);

medium

A. test

B. Undefined behavior (may print garbage or crash)

C. Compilation error

D. Empty string

Solution

1. Step 1: Analyze memory allocation and free

   Memory is allocated and string "test" copied. Then memory is freed.

2. Step 2: Using pointer after free

   Printing ptr after free causes undefined behavior; it may print garbage or crash.

3. Final Answer:

   Undefined behavior (may print garbage or crash) -> Option B

4. Quick Check:

   Using freed pointer = undefined behavior [OK]

Hint: Never use pointer after free without reassigning [OK]

Common Mistakes:

• Assuming freed pointer still holds valid data
• Expecting compilation error
• Thinking it prints empty string

4. Identify the error in this code snippet:

int *arr = malloc(3 * sizeof(int));
free(arr + 1);

medium

A. free called on pointer not returned by malloc

B. Missing free call

C. Incorrect size in malloc

D. No error, code is correct

Solution

1. Step 1: Understand pointer passed to free

   Memory was allocated at arr, but free is called on arr + 1, which is not the original pointer.

2. Step 2: Free must be called on original pointer

   Only the pointer returned by malloc (or NULL) can be passed to free safely.

3. Final Answer:

   free called on pointer not returned by malloc -> Option A

4. Quick Check:

   Free must use original pointer = A [OK]

Hint: Free only original malloc pointer, not offset pointers [OK]

Common Mistakes:

• Freeing pointer offset from malloc result
• Not freeing allocated memory
• Assuming free can take any pointer inside block

5. You have a function that reallocates memory for an integer array:

int *resize(int *arr, int new_size) {
    int *temp = realloc(arr, new_size * sizeof(int));
    if (temp == NULL) {
        free(arr);
        return NULL;
    }
    return temp;
}

What is the best practice to avoid memory leaks when using this function?

hard

A. Always free the original pointer before calling resize

B. Call free on the returned pointer immediately after resize

C. Assign the return value to a temporary pointer before updating original pointer

D. Do not check if realloc returns NULL

Solution

1. Step 1: Understand realloc behavior

   If realloc fails, it returns NULL and original memory remains allocated.

2. Step 2: Use temporary pointer to avoid losing original memory

   Assign realloc result to a temp pointer first; if NULL, free original to avoid leaks.

3. Final Answer:

   Assign the return value to a temporary pointer before updating original pointer -> Option C

4. Quick Check:

   Use temp pointer for realloc to prevent leaks = B [OK]

Hint: Use temp pointer for realloc result before replacing original [OK]

Common Mistakes:

• Overwriting original pointer without checking realloc result
• Freeing original pointer before realloc
• Ignoring NULL return from realloc