What is the time complexity of memory allocation assumed to be?

Question

It is well-known that dynamic arrays have an amortized $O(1)$ time complexity for adding one item, but a worst-case $O(n)$ complexity. This is because for particular values of $n$, there is no more room in the buffer, so the dynamic array allocates a new buffer and copies over $n$ items.

My question is, what would the worst-case complexity be if it didn't have to copy over $n$ items? If it only needed to allocate a buffer with size $O(n)$ when resizing, would that be considered to run $O(1)$ or $O(n)$ time?

Answer 1

what would the worst-case complexity be if it didn't have to copy over $n$ items? If it only needed to allocate a buffer with size $O(n)$ when resizing, would that be considered to run $O(1)$ or $O(n)$ time?

This depends on what you mean by "allocate a buffer with size $O(n)$" and how much time that takes. Unfortunately, there isn't a standard answer for that. It boils down to how you model "allocating a buffer", and your assumption about the time complexity of that operation.

You could assume that allocating such a buffer could be done in $O(1)$, or you could assume that this takes $\Theta(n)$ time. It depends on the system you're trying to model:

• The operating system will generally overwrite memory that has previously been used by another process with all zeros to avoid leaking information from one process to another. Thus, allocating a size-$n$ buffer will take at least $\Omega(n)$ time due to this initialization procedure.

• If you are working in a very low-level setting (for instance assembly programming), "allocating a buffer" might you mean grabbing a pointer to the top of the heap and then incrementing that pointer by the number of elements you want to allocate. You could reasonably model this as an $O(1)$ operation.

• If you are, for instance, working in C and initialize a buffer by calling malloc, then there is generally no guarantee about the complexity of this operation. It might take $O(1)$ time, $O(n)$, $O(n^2)$, exponential time or even fail to allocate the buffer at all (out of memory). On the other hand, specialized implementations of malloc (such as TLSF) might come with guarantees.

Thus, depending on the implementation, the operation "allocating a buffer" should be modeled as having a different time complexity. If you are working in a purely theoretical setting (without any underlying implementation), then you have to make an assumption. Assuming it takes $O(n)$ time is more reasonable than assuming it would take $O(1)$ time (since more real-world systems will be able to meet the former assumption than the latter), however, any assumption, if clearly stated is valid. It is even possible to reason about totally unreasonable assumptions (for instance, you could assume that you could copy over $n$ items in $O(1)$ time) for the sake of argument.