Memory allocation and deallocation in C++ - Time & Space Complexity

Time Complexity: Memory allocation and deallocation

O(n)

Understanding Time Complexity

When we allocate or free memory in a program, it takes some time. Understanding how this time grows helps us write faster programs.

We want to know how the cost of memory allocation and deallocation changes as the program runs more or uses more memory.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int* allocateArray(int n) {
    int* arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = 0;
    }
    return arr;
}

void freeArray(int* arr) {
    delete[] arr;
}
    

This code allocates an array of size n, initializes it, and then frees the memory.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that sets each element to zero.
• How many times: It runs exactly n times, once for each element.

How Execution Grows With Input

As n grows, the number of times we set elements grows the same way.

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

Pattern observation: The work grows directly with n, so doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to allocate and initialize memory grows in a straight line with the size of the array.

Common Mistake

[X] Wrong: "Memory allocation is always a constant time operation, no matter the size."

[OK] Correct: Allocating memory often involves setting up space and initializing it, which takes time proportional to the size requested.

Interview Connect

Understanding how memory operations scale helps you write efficient code and explain your choices clearly in interviews.

Self-Check

"What if we removed the loop that initializes the array? How would the time complexity change?"

Practice

1. What does the new operator do in C++?

easy

A. Allocates memory on the heap for a variable or object

B. Deletes a variable from memory

C. Allocates memory on the stack

D. Copies data from one variable to another

Solution

1. Step 1: Understand the role of new

   The new operator allocates memory dynamically on the heap during program execution.

2. Step 2: Differentiate from other memory actions

   It does not delete memory or allocate on the stack; it only reserves space on the heap.

3. Final Answer:

   Allocates memory on the heap for a variable or object -> Option A

4. Quick Check:

   new = allocate heap memory [OK]

Hint: Remember: new = allocate memory on heap [OK]

Common Mistakes:

• Confusing new with delete
• Thinking new allocates on stack
• Assuming new copies data

2. Which of the following is the correct syntax to deallocate memory allocated with new for a single integer variable?

easy

A. delete[] ptr;

B. free(ptr);

C. delete ptr;

D. ptr = nullptr;

Solution

1. Step 1: Identify correct deallocation for single object

   Memory allocated with new for a single variable must be freed with delete, not delete[].

2. Step 2: Exclude incorrect options

   free() is for C-style malloc, and setting pointer to nullptr does not free memory.

3. Final Answer:

   delete ptr; -> Option C

4. Quick Check:

   Single object deallocation = delete [OK]

Hint: Use delete for single object, delete[] for arrays [OK]

Common Mistakes:

• Using delete[] for single variable
• Using free() instead of delete
• Only setting pointer to nullptr without delete

3. What is the output of the following code?

int* ptr = new int(10);
std::cout << *ptr << std::endl;
delete ptr;

medium

A. 0

B. 10

C. Garbage value

D. Compilation error

Solution

1. Step 1: Analyze memory allocation and initialization

   The pointer ptr points to a new integer initialized with 10.

2. Step 2: Understand output before deletion

   Dereferencing *ptr prints 10 before memory is deleted.

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Dereference new int(10) = 10 [OK]

Hint: Dereference pointer before delete to see value [OK]

Common Mistakes:

• Assuming output is 0 or garbage
• Thinking delete affects output before cout
• Confusing syntax causing compile error

4. Identify the error in the following code snippet:

int* arr = new int[5];
delete arr;

medium

A. Pointer arr is not initialized

B. Memory is not allocated properly

C. No error, code is correct

D. Should use delete[] instead of delete

Solution

1. Step 1: Check allocation type

   Memory allocated with new[] must be deallocated with delete[].

2. Step 2: Identify mismatch in deallocation

   Using delete instead of delete[] causes undefined behavior.

3. Final Answer:

   Should use delete[] instead of delete -> Option D

4. Quick Check:

   Array deallocation = delete[] [OK]

Hint: Match new[] with delete[] always [OK]

Common Mistakes:

• Using delete for arrays
• Ignoring pointer initialization
• Assuming no error in mismatched delete

5. You want to allocate memory for an array of 10 integers and initialize all elements to zero. Which code snippet correctly does this and safely deallocates the memory?

hard

A. int* arr = new int[10](); delete[] arr;

B. int* arr = new int[10]; delete arr;

C. int* arr = (int*)malloc(10 * sizeof(int)); delete[] arr;

D. int* arr = new int(10); delete[] arr;

Solution

1. Step 1: Allocate and initialize array to zero

   Using new int[10]() allocates an array of 10 integers and initializes all to zero.

2. Step 2: Properly deallocate array memory

   Memory allocated with new[] must be freed with delete[] to avoid leaks or undefined behavior.

3. Final Answer:

   int* arr = new int[10](); delete[] arr; -> Option A

4. Quick Check:

   new[] with () + delete[] = safe zero-init array [OK]

Hint: Use new int[size]() and delete[] for arrays [OK]

Common Mistakes:

• Using delete instead of delete[] for arrays
• Mixing malloc/free with new/delete
• Allocating single int instead of array