Questions About Running time

Question

What is the running time in big-O notation of:

vector.push_back(item)

and

vec.erase(itr)  // itr points in the middle of a vector

Answer 1

O(1) (amortized time, reallocation may happen) in case of push_back()

O(n) in case of erase() i.e Linear on the number of elements erased (destructors) plus the number of elements after the last element deleted (moving).

Answer 2

For "vector.push_back(item)" its only O(1). And "vec.erase(itr)" O(n) because later elements are shifted down.

Edit: If it points on the middle in the vector, its like O(n/2).

Answer 3

From http://www.sgi.com/tech/stl/Vector.html:

A vector is a Sequence that supports random access to elements, constant time insertion and removal of elements at the end, and linear time insertion and removal of elements at the beginning or in the middle.