4 ms·
The claim is that vectors perform better than lists even in a case where the theoretical complexity is in favor of the list: insertion in the middle. However th
by Thomashuet 4y ago
The claim is that vectors perform better than lists even in a case where the theoretical complexity is in favor of the list: insertion in the middle. However the complexity of insertion in the middle is O(n) for both vectors and lists so the demonstration falls apart.
A scenario where the complexity is different would be to copy and modify the first element: O(1) for lists and O(n) for vectors.
- gpderetta 4y agoInsertion in a linked list is not O(n) though.
- sliken 4y agoThe post mentions inserting in the middle of the list. Sort of, do you assume you found the right node already, then it's O(1). If not, it's O(n/2).
- gpderetta 4y agoInserting in the middle of the list is still O(1). It doesn't make sense to include finding the insertion position in the insert cost as there are many ways to do that (for example you might have a separate hashed or ordered index, or simply have a pointer to the node by other means). Also, pedantically O(n/2) is the same as O(n).