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

title self-explanatory. easy question. think it's o(n) wanted verify before final tomorrow.

the short answer is... depends.

if q pointer array of objects have destructors, delete[] q need call of destructors. call o(n) destructors, n number of elements in array. on other hand, if q points array of objects don't have destructors (for example, ints or simple structs), no destructors need called, takes o(1) time.

now note destructors don't have run in o(1) time each. if objects are, say, std::vector objects, each destructor in turn has fire off more deallocations. without knowing more objects are, can if there destructors called, there 0 destructors called if destructors trivial , o(n) destructors called otherwise.

but ignores implementation detail of how heap allocator works. it's possible deallocating block of memory might take o(log k) time, k total number of allocated blocks, or might take o(1) time regardless of how many blocks of memory there are, or might take o(log log k), etc. without knowing how allocator works, can't sure.

in short, if focus purely on work required clean objects before handing block memory allocator, there o(n) destructors called if objects stored have destructors , 0 destructors called otherwise. these destructors might take nontrivial amount of time complete. then, there's cost of reintroducing block of memory memory allocator, might take own amount of time.

hope helps!