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?"