7

Insertion on std::list is claimed to be constant time, regardless whether it is made in the front, middle or back of the container.

On the other hand, acquisition of memory for the new inserted item is handled by the standard allocator, which uses operator new. AFAIK operator new is not guaranteed to have constant time.

When operator new looks for available space in the heap, it must be sure that it will not override previously allocated memory, therefore it has to keep track of what has already been allocated on the heap. I conclude that insertion must be at least linear on the number of elements already in the list.

What is wrong with this reasoning?

My question reads:

  • How is it possible to say that insertion on lists is constant time, when acquiring memory for each new node is not guaranteed to be constant time?
Filip Roséen - refp
  • 62,493
  • 20
  • 150
  • 196
mzimbres
  • 141
  • 2
  • 6
  • 3
    I believe allocating a constant amount of memory *is* in fact constant time. But I guess a more precise runtime bound would be *O(size of inserted object)*, because you might need to copy it. Then again, since all the struct/class sizes are defined at compile time, they could be considered bounded in some sense – Niklas B. Mar 16 '14 at 18:24
  • 8
    the allocation of memory by `new` is unrelated to the size of the list. Constant time means unrelated to the size of input. In other words, `new` is not faster to allocate if there is 1 element in the list, and slower to allocate if there is 1M elements in the list. The two operations are unrelated. – Kevin Mar 16 '14 at 18:26
  • 3
    Regarding your expectation about the complexity of memory allocation, you should search for memory management topics on your favourite search engine. Sadly, far too many CS courses neglect teaching basic allocation algorithms. – DanielKO Mar 16 '14 at 18:37
  • 3
    std::list is a doubly linked list. Nodes are not allocated in contiguous chunks of memory. By constant time, what they actually mean is allocation is indifferent to the size of the of the list. It doesn't mean that it will always take the same amount of time to allocate memory for a new node. That would depend on the memory management technique being used and the arrangement of the available memory at that moment. – vaibhav kumar Mar 16 '14 at 19:22
  • So should I conclude that the algorithm used to implement "new" does not depend on the number of objects already allocated on the heap? Does the standard specify that? In that case I would agree that insertion is constant time in std::list. – mzimbres Mar 16 '14 at 21:57
  • Also note that even in theory linked list insertions are O(1) and dynamic array instertions are O(n), in practice the later performs far better due to its usage of the memory hierarchy. – Manu343726 Mar 20 '14 at 09:27
  • 2
    Most sane allocation schemes keep track of the pieces of *free* memory available, *not* what has already been allocated. – SoapBox Mar 20 '14 at 09:31

2 Answers2

3

Note: It is important to note the difference between "real life time" and the "time" talked about when diving into time complexity. When time complexity is the topic it's important that one doesn't confuse the usage of "time" with "milliseconds spent doing something".

WHAT IS THE DEFINITION OF constant time?

Wikipedia is often said to be a bad reference in many contexts, but in this case (and a lot of others) the definitions available is correct and will help to describe how things work.

The article about time complexity says the following about constant time:

Wikipedia - Constant Time

An algorithm is said to be constant time (also written as O(1) time) if the value of T(n) is bounded by a value that does not depend on the size of the input. For example, accessing any single element in an array takes constant time as only one operation has to be performed to locate it.

Since the insertion into a std::list does not depend on the number of elements in the list we say that insertion is constant time; each insertion, no matter where or when, consists of the same number of elementary operations; none related to the size of the list.

But what if operator new is not O(1)?

Honestly it doesn't matter, even if the complexity of new would implicitly depend on how many previous entities we have allocated, the complexity of our list-insertion will be unchanged. The allocation is indifferent to the size of the list.

O(1), constant time, means that the time to execute something is unrelated to the size of input in any given algorithm. Even if new isn't O(1), our insertation is O(1) since it only describes itself.

The paths taken inside our list inseration all includes operator new. The path doesn't change because of the size of our list, the path's complexity is constant time.

So what are we dealing with?

Hannibal_Smith in ##c++ at freenode said something clever, and I liked it so much that I will include it in this post: The cost model is a pointer machine.

Even though the sentence might be a little bit misleading it does serve the purpose of explaining how the insertion is O(1) even though parts of the algorithm isn't constant time.

The insertion into a std::list is described from the perspective of being a machine who only deals with pointers, and from this perspective one cannot say that it is nothing other than O(1). The allocation done inside this algorithm is not related to the complexity of the algorithm itself.

Filip Roséen - refp
  • 62,493
  • 20
  • 150
  • 196
  • 2
    I found the second section of your answer extremely unsatisfactory, even though I've struggled in vain to come up with a better formulation. It also disagrees with your first section: If a subroutine called unconditionally in your algorithm is `O(n)` in time complexity, then your algorithm is **not** `O(1)`. – microtherion Mar 20 '14 at 09:12
  • I've now tried to give my take on the answer. Feel free to downvote *me* if you're similarly unpersuaded ;-) – microtherion Mar 20 '14 at 09:22
  • @microtherion You are wrong.. the complexity of an algorithm is describing that of itself. If a subroutine is called that has `O(n)` complexity that only applies to the enclosing algorithms complexity if the algorithm is responsible for that `n`. Let me repeat: **"Even if new isn't O(1) our insertion is O(1) since it only describes itself"**. – Filip Roséen - refp Mar 20 '14 at 09:39
  • @microtherion see my added section titled *"So what are we dealing with?"*. – Filip Roséen - refp Mar 20 '14 at 09:46
1

This is a very tricky question that has been discussed at some length in this thread.

If I could try to summarize it: The standard makes some subtle distinctions. If you read it precisely, some operations are indeed specified to be "constant time", but std::list insertion is not among them. It is specified to be "constant" (Edit: wrong, see below) and the "General Container Requirements" clause (23.2.1 in this draft of the C++ standard) explains that

All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects.

(Edit: as Filip Roséen pointed out, I was mistaken; std::list insertion is specified to be "constant time", but I believe the General Requirements clause still governs). So because list insertion only has to work on a single object and its neighbors, it's "constant complexity" even though it may not necessarily be "constant time complexity" because there are no time complexity guarantees for the allocation.

Pragmatically, a decent memory allocator will not be linear in the number of objects allocated, though it probably is not constant time either.

Community
  • 1
  • 1
microtherion
  • 3,938
  • 1
  • 15
  • 18
  • +1 for the last sentence. Memory allocation is not O(1), so strictly speaking list insert also can't be. In many real-world scenarios the memory allocation overhead is simply not big enough to be of any concern, but if the stress put on the allocator is very high, it can make a measurable difference. – ComicSansMS Mar 20 '14 at 09:32
  • **-1**. This answer is not inaccurate but it's funny how you link to a thread discussing one thing, where the conclusion is the opposite of what you are saying in your post. It's also wrong, the standard does say that insertion to a `std::list` is **constant time**, `[list.overview]p1` and `[list.modifiers]`, among others. – Filip Roséen - refp Mar 20 '14 at 09:34
  • @FilipRoséen-refp **was** the conclusion the opposite? I read the discussion as expressing a range of opinions, and I picked the one which to me seemed best founded. You are right about what the standard says, though; I looked up the wrong operation and will correct my answer. – microtherion Mar 20 '14 at 09:48
  • @microtherion if one links to a question it's often implied that the accepted answer and the question go together, and that that is what you are agreeing with. link directly to suitable answers if you'd like to avoid this misunderstanding. – Filip Roséen - refp Mar 20 '14 at 09:50