### Time complexity in STL

while adding ,removing and updating (at first/last/in between) data in vector, list or in simple array, what is the time complexity?
Linked list: O(1) -> No defference for first, last or between

for arrays, adding/removing a data is meaningless because it has a fixed length. If you mean e.g. adding/removing (actually updating) element[5] of a 10-element array, it is O(1);
 Linked list: O(1) -> No defference for first, last or between

For "between" to be O(1) this assumes that you already have an iterator to that position, or that the position is a fixed distance from the beginning or end of the list. Inserting/removing an element in a list at a random position (without having an iterator) is O(N) because you would have to start from the beginning or end of the list and step through the list until you come to the correct position.

Adding an element to the end of a vector is O(1), amortized time.
Removing an element at the end of a vector is O(1).
Adding an element to the first or at a random location is O(N).
Removing an element from the first or at a random location is O(N) because it will have to move all the elements after the removed element one step. If the order of the elements in the vector doesn't matter you can do it in O(1) by just putting the last element at the position of the removed element and decrease the size of the vector by one.
Last edited on
Topic archived. No new replies allowed.