Is Big-O of the C++ statement 'delete [] Q;' O(1) or O(n)?

Question

Title is self-explanatory. Very easy question. I think it's O(n) but wanted to verify before my final tomorrow.

Answer 1

The short answer is... it depends.

If Q is a pointer to an array of objects that have destructors, then delete[] Q will need to call all of those destructors. This will call O(n) destructors, where n is the number of elements in the array. On the other hand, if Q points to an array of objects that don't have destructors (for example, ints or simple structs), then no destructors need to be called, which takes only O(1) time.

Now note that those destructors don't have to run in O(1) time each. If the objects are, say, std::vector objects, then each destructor in turn has to fire off more deallocations. Without knowing more about what those objects are, all we can say is that if there are destructors called, there will be 0 destructors called if the destructors are trivial and O(n) destructors called otherwise.

But this ignores the implementation detail of how the heap allocator works. It's possible that deallocating a block of memory might take O(log K) time, where K is the total number of allocated blocks, or it might take O(1) time regardless of how many blocks of memory there are, or it might take O(log log K), etc. Without knowing how the allocator works, you honestly can't be sure.

In short, if you focus purely on the work required to clean up the objects before handing the block back to the memory allocator, there are O(n) destructors called if the objects stored have destructors and 0 destructors called otherwise. These destructors might take a nontrivial amount of time to complete. Then, there's the cost of reintroducing the block of memory back into the memory allocator, which might take its own amount of time.

Hope this helps!