Questions About Running time

问题:

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

回答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).

回答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).

回答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.