malloc function - Time & Space Complexity

Time Complexity: malloc function

O(n)

Understanding Time Complexity

When we use malloc in C, it asks the system for memory space. Understanding how long this takes helps us write faster programs.

We want to know how the time to get memory changes as the requested size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdlib.h>

int main() {
    int n = 1000;
    int *arr = (int *)malloc(n * sizeof(int));
    if (arr == NULL) {
        return 1; // allocation failed
    }
    // use arr ...
    free(arr);
    return 0;
}
    

This code asks the system to reserve space for 1000 integers using malloc.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The malloc function internally searches for a free memory block large enough to fit the requested size.
• How many times: This search happens once per call, but may involve checking multiple memory blocks depending on the allocator's state.

How Execution Grows With Input

As the requested size grows, malloc may need to look through more memory blocks to find a fit.

Input Size (bytes)	Approx. Operations
100	Few checks, fast allocation
1,000	More checks, takes longer
10,000	Even more checks, slower

Pattern observation: The time to allocate grows roughly with how many free blocks the system must check, which can increase with requested size.

Final Time Complexity

Time Complexity: O(n)

This means the time to allocate memory grows linearly with the size requested or the number of free blocks checked.

Common Mistake

[X] Wrong: "malloc always runs instantly no matter the size."

[OK] Correct: Actually, malloc may take longer for bigger requests because it searches for a suitable free space, so time can grow with size.

Interview Connect

Understanding how memory allocation time grows helps you write efficient programs and shows you know how system resources work behind the scenes.

Self-Check

"What if we used a custom memory pool instead of malloc? How would the time complexity change?"

Practice

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

easy

A. Declares a variable

B. Frees previously allocated memory

C. Allocates a block of memory dynamically during program execution

D. Prints output to the screen

Solution

1. Step 1: Understand the purpose of malloc

   The malloc function is used to allocate memory dynamically while the program is running, not at compile time.

2. Step 2: Differentiate malloc from other functions

   Unlike free which releases memory, or printf which outputs text, malloc only allocates memory.

3. Final Answer:

   Allocates a block of memory dynamically during program execution -> Option C

4. Quick Check:

   malloc = allocate memory [OK]

Hint: malloc is for getting memory, free is for releasing it [OK]

Common Mistakes:

• Confusing malloc with free
• Thinking malloc prints output
• Assuming malloc declares variables

2. Which of the following is the correct syntax to allocate memory for 10 integers using malloc?

easy

A. int *ptr = malloc(10 * sizeof(int));

B. int *ptr = malloc(10);

C. int ptr = malloc(10 * sizeof(int));

D. int *ptr = malloc(sizeof(int));

Solution

1. Step 1: Calculate correct size for allocation

   To allocate memory for 10 integers, multiply 10 by the size of an integer using sizeof(int).

2. Step 2: Use correct pointer type and syntax

   The pointer must be declared as int * and assigned the result of malloc. int *ptr = malloc(10 * sizeof(int)); correctly does this.

3. Final Answer:

   int *ptr = malloc(10 * sizeof(int)); -> Option A

4. Quick Check:

   malloc size = count * sizeof(type) [OK]

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

Common Mistakes:

• Not multiplying by sizeof(int)
• Using wrong pointer type
• Allocating too little memory

3. What will be the output of the following code?

int *p = malloc(4 * sizeof(int));
if (p == NULL) {
    printf("Allocation failed\n");
} else {
    p[0] = 10;
    p[1] = 20;
    printf("%d %d\n", p[0], p[1]);
}
free(p);

medium

A. Compilation error

B. Allocation failed

C. 0 0

D. 10 20

Solution

1. Step 1: Check if malloc succeeded

   The code checks if p is NULL. If not NULL, allocation succeeded and memory can be used.

2. Step 2: Assign and print values

   Values 10 and 20 are assigned to p[0] and p[1]. Then they are printed, so output is "10 20".

3. Final Answer:

   10 20 -> Option D

4. Quick Check:

   malloc success prints assigned values [OK]

Hint: Check for NULL before using malloc memory [OK]

Common Mistakes:

• Ignoring NULL check
• Printing uninitialized memory
• Forgetting to free memory

4. Identify the error in this code snippet:

char *str = malloc(5);
strcpy(str, "Hello World");
printf("%s", str);
free(str);

medium

A. strcpy is not allowed with malloc

B. malloc size is too small for the string

C. free should be called before strcpy

D. printf format specifier is wrong

Solution

1. Step 1: Check allocated memory size

   The string "Hello World" needs 12 bytes (11 chars + 1 for '\0'), but only 5 bytes are allocated.

2. Step 2: Understand consequences of small allocation

   Copying a larger string into smaller allocated memory causes buffer overflow and undefined behavior.

3. Final Answer:

   malloc size is too small for the string -> Option B

4. Quick Check:

   Allocate enough memory for string + '\0' [OK]

Hint: Allocate string length + 1 for null terminator [OK]

Common Mistakes:

• Allocating less memory than string length
• Calling free before using memory
• Wrong printf format for strings

5. You want to create a dynamic array of integers that doubles its size when full. Which approach correctly uses malloc and realloc to achieve this?

hard

A. Start with malloc for initial size, then use realloc to double size when needed

B. Use malloc once with maximum size needed upfront

C. Use realloc first, then malloc to allocate memory

D. Use malloc repeatedly without freeing old memory

Solution

1. Step 1: Allocate initial memory with malloc

   Start by allocating memory for the initial array size using malloc.

2. Step 2: Use realloc to resize when array is full

   When the array is full, use realloc to double the memory size safely without losing data.

3. Step 3: Avoid incorrect usage

   Using malloc repeatedly without freeing old memory causes leaks, allocating maximum size upfront wastes memory, and using realloc before malloc is incorrect.

4. Final Answer:

   Start with malloc for initial size, then use realloc to double size when needed -> Option A

5. Quick Check:

   malloc first, then realloc to grow [OK]

Hint: malloc once, then realloc to grow array safely [OK]

Common Mistakes:

• Calling realloc before malloc
• Allocating max size upfront wasting memory
• Not freeing old memory causing leaks