delete operator in C++ - Time & Space Complexity

Time Complexity: delete operator

O(1)

Understanding Time Complexity

When using the delete operator in C++, it's important to understand how its execution time grows as the program runs.

We want to know how the cost of deleting memory changes with the size or number of objects involved.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int* arr = new int[100];
// ... use the array ...
delete[] arr;

int* single = new int;
// ... use the single int ...
delete single;
    

This code allocates memory for an array and a single integer, then frees that memory using delete[] and delete.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The delete[] and delete operators deallocate the memory blocks.
• How many times: Each runs once, regardless of the array size.

Both the delete[] for the array and delete for a single object run once, so they are constant time.

How Execution Grows With Input

As the number of elements in the array grows, the time to delete remains constant for primitive types.

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

Pattern observation: The time to delete an array is constant, independent of its size (for primitive types).

Final Time Complexity

Time Complexity: O(1)

This means deleting an array or a single object takes constant time (for primitive types like int).

Common Mistake

[X] Wrong: "Deleting an array always takes O(n) time proportional to its size."

[OK] Correct: For primitive types like int, delete[] deallocates the entire memory block in constant time, as there are no non-trivial destructors to call for each element.

Interview Connect

Understanding how delete works helps you write efficient code and avoid surprises in performance when managing memory.

Self-Check

"What if we used smart pointers instead of raw pointers? How would the time complexity of deleting change?"

Practice

1. What is the main purpose of the delete operator in C++?

easy

A. To allocate new memory

B. To free memory allocated with new

C. To copy objects

D. To declare variables

Solution

1. Step 1: Understand memory allocation

   The new operator allocates memory dynamically on the heap.

2. Step 2: Role of delete

   The delete operator frees that allocated memory to avoid leaks.

3. Final Answer:

   To free memory allocated with new -> Option B

4. Quick Check:

   delete frees memory [OK]

Hint: Remember: new allocates, delete frees memory [OK]

Common Mistakes:

• Confusing delete with new
• Using delete to copy objects
• Thinking delete declares variables

2. Which of the following is the correct syntax to delete a dynamically allocated array arr?

easy

A. delete arr;

B. delete array arr;

C. delete arr[];

D. delete[] arr;

Solution

1. Step 1: Identify array deletion syntax

   For arrays allocated with new[], use delete[] to free all elements properly.

2. Step 2: Match correct syntax

   delete[] arr; correctly deletes the entire array.

3. Final Answer:

   delete[] arr; -> Option D

4. Quick Check:

   Use delete[] for arrays [OK]

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

Common Mistakes:

• Using delete instead of delete[] for arrays
• Placing brackets after variable name incorrectly
• Writing delete array arr (invalid syntax)

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

int* p = new int(10);
std::cout << *p << std::endl;
delete p;
// std::cout << *p << std::endl; // Uncommenting this line causes what?

medium

A. 10 and then 10 again

B. Compilation error at delete

C. 10 and then undefined behavior

D. Runtime error at new

Solution

1. Step 1: Analyze output before delete

   The pointer p points to an int with value 10, so *p prints 10.

2. Step 2: Effect of delete and accessing pointer

   After delete p;, the memory is freed. Accessing *p after delete causes undefined behavior (may crash or print garbage).

3. Final Answer:

   10 and then undefined behavior -> Option C

4. Quick Check:

   Access after delete = undefined behavior [OK]

Hint: Don't use pointer after delete; it's unsafe [OK]

Common Mistakes:

• Assuming deleted pointer still holds valid data
• Expecting compilation error on delete
• Ignoring undefined behavior risks

4. Identify the error in this code snippet:

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

medium

A. Should use delete[] instead of delete

B. Should use delete without brackets

C. No error, code is correct

D. Should not delete dynamically allocated arrays

Solution

1. Step 1: Check allocation type

   arr is allocated with new int[5], which creates an array.

2. Step 2: Correct deletion method

   Arrays must be deleted with delete[] arr; to properly free all elements.

3. Final Answer:

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

4. Quick Check:

   Array delete needs delete[] [OK]

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

Common Mistakes:

• Using delete for arrays causes undefined behavior
• Thinking delete works for both single and arrays
• Ignoring memory leaks from wrong delete

5. Consider this code:

int** matrix = new int*[3];
for (int i = 0; i < 3; ++i) {
    matrix[i] = new int[4];
}
// Code to delete matrix properly?

Which is the correct way to delete all allocated memory?

hard

A. for (int i = 0; i < 3; ++i) delete[] matrix[i]; delete[] matrix;

B. for (int i = 0; i < 3; ++i) delete matrix[i]; delete[] matrix;

C. delete[] matrix; delete[] matrix[0];

D. delete matrix; delete matrix[0];

Solution

1. Step 1: Understand allocation

   Each matrix[i] is an array allocated with new int[4], so must be deleted with delete[].

2. Step 2: Delete outer array

   The matrix pointer itself is an array of pointers allocated with new int*[3], so delete with delete[] matrix;.

3. Final Answer:

   for (int i = 0; i < 3; ++i) delete[] matrix[i]; delete[] matrix; -> Option A

4. Quick Check:

   Match new[] with delete[] at all levels [OK]

Hint: Delete inner arrays with delete[], then outer with delete[] [OK]

Common Mistakes:

• Using delete instead of delete[] for inner arrays
• Deleting outer array with delete instead of delete[]
• Forgetting to delete inner arrays causing leaks