Dynamic memory allocation (heap) in Compiler Design - Time & Space Complexity

Time Complexity: Dynamic memory allocation (heap)

O(n)

Understanding Time Complexity

When a program requests memory during its run, it uses dynamic memory allocation on the heap. Understanding how the time to allocate or free memory grows helps us know how efficient this process is.

We want to find out how the time needed changes as the program asks for more or larger memory blocks.

Scenario Under Consideration

Analyze the time complexity of the following heap allocation code snippet.

void* allocate(int size) {
  Block* block = find_free_block(size); // search free list
  if (block == NULL) {
    block = request_from_os(size); // get new memory
  }
  mark_as_used(block);
  return block->address;
}
    

This code tries to find a free memory block of the requested size on the heap. If none is found, it asks the operating system for more memory.

Identify Repeating Operations

Look for repeated work that affects time.

• Primary operation: Searching the free list for a suitable block.
• How many times: This search may check many blocks, depending on the free list size.

How Execution Grows With Input

As the program runs and requests more memory, the free list can grow longer, making the search take more time.

Input Size (n)	Approx. Operations
10	About 10 checks in free list
100	About 100 checks
1000	About 1000 checks

Pattern observation: The time to find a free block grows roughly in direct proportion to the number of free blocks.

Final Time Complexity

Time Complexity: O(n)

This means the time to allocate memory grows linearly with the number of free blocks to check.

Common Mistake

[X] Wrong: "Allocating memory always takes constant time because the OS handles it quickly."

[OK] Correct: The program often searches a list of free blocks first, which can take longer as more blocks exist, so allocation time depends on this search.

Interview Connect

Understanding how dynamic memory allocation time grows helps you explain real-world program performance and shows you can think about resource management clearly.

Self-Check

"What if the free blocks were stored in a balanced tree instead of a list? How would the time complexity change?"

Practice

1. What is the main purpose of dynamic memory allocation in programming?

easy

A. To store program instructions permanently

B. To allocate memory only at the start of the program

C. To allocate memory during program execution as needed

D. To speed up the compilation process

Solution

1. Step 1: Understand dynamic memory allocation

   Dynamic memory allocation allows a program to request memory while it is running, not just before it starts.

2. Step 2: Compare with static allocation

   Static allocation reserves memory only at compile time or program start, unlike dynamic allocation which is flexible during execution.

3. Final Answer:

   To allocate memory during program execution as needed -> Option C

4. Quick Check:

   Dynamic allocation = allocate memory at runtime [OK]

Hint: Dynamic means memory allocated while program runs [OK]

Common Mistakes:

• Confusing dynamic with static allocation
• Thinking memory is allocated only once at start
• Assuming dynamic allocation speeds up compilation

2. Which of the following is the correct way to allocate memory dynamically in C language?

easy

A. int ptr = new int;

B. int ptr = malloc(int);

C. int *ptr = allocate(int);

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

Solution

1. Step 1: Recall C dynamic memory syntax

   In C, malloc is used with the size in bytes, e.g., malloc(sizeof(int)).

2. Step 2: Check each option

   int *ptr = malloc(sizeof(int)); uses correct syntax with pointer and malloc. Others use incorrect functions or syntax.

3. Final Answer:

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

4. Quick Check:

   C malloc syntax = int *ptr = malloc(sizeof(type)) [OK]

Hint: malloc needs pointer and size in bytes [OK]

Common Mistakes:

• Using malloc without sizeof
• Assigning malloc result to non-pointer
• Using non-C functions like allocate or new

3. Consider this C code snippet:

int *p = malloc(3 * sizeof(int));
p[0] = 10;
p[1] = 20;
p[2] = 30;
printf("%d", p[1]);

What will be the output?

medium

A. 20

B. 10

C. 30

D. Runtime error

Solution

1. Step 1: Understand memory allocation and indexing

   Memory for 3 integers is allocated. Values assigned are p[0]=10, p[1]=20, p[2]=30.

2. Step 2: Identify printed value

   The printf prints p[1], which is 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   p[1] = 20 printed [OK]

Hint: Array index 1 holds second value assigned [OK]

Common Mistakes:

• Confusing p[0] with p[1]
• Expecting runtime error without free()
• Misunderstanding pointer indexing

4. Identify the error in this C code snippet:

int *ptr;
*ptr = 5;
ptr = malloc(sizeof(int));

medium

A. Memory is allocated after dereferencing pointer

B. malloc syntax is incorrect

C. Pointer is not declared

D. No error, code is correct

Solution

1. Step 1: Analyze pointer usage order

   The code dereferences ptr before allocating memory with malloc.

2. Step 2: Understand consequences

   Dereferencing an uninitialized pointer causes undefined behavior or crash.

3. Final Answer:

   Memory is allocated after dereferencing pointer -> Option A

4. Quick Check:

   Dereference before malloc = error [OK]

Hint: Always malloc before using pointer dereference [OK]

Common Mistakes:

• Ignoring pointer initialization order
• Thinking malloc syntax is wrong
• Assuming no error without free()

5. You want to store a list of names where the number of names is unknown at compile time. Which approach best uses dynamic memory allocation?

hard

A. Allocate a fixed-size array large enough for all names

B. Use malloc to allocate memory for each name as it is added

C. Declare all names as global variables

D. Use static arrays inside functions

Solution

1. Step 1: Understand problem requirements

   The number of names is unknown, so fixed-size arrays may waste memory or be insufficient.

2. Step 2: Choose dynamic allocation strategy

   Allocating memory for each name as it is added allows flexible, efficient use of heap memory.

3. Final Answer:

   Use malloc to allocate memory for each name as it is added -> Option B

4. Quick Check:

   Unknown size = allocate dynamically per item [OK]

Hint: Allocate memory as data arrives, not fixed size [OK]

Common Mistakes:

• Using fixed arrays wasting memory
• Declaring globals wastes flexibility
• Using static arrays limits size