I'm trying to calculate complexity of some algorithms but I don't no how to mesure the complexity of the operations with vectors. For example, what is the complexity of push_back()?
In c++ reference I found "Constant (amortized time, reallocation may happen). If a reallocation happens, the reallocation is itself up to linear in the entire size."
What does it's means? Is the operation of complexity O(n)? (n is the vector length).
Thank you.
Complexities for vector are:
You have reallocation when size of vector is greater than:
size_type capacity() const;
Returns: The total number of elements that the vector can hold without requiring reallocation.
Notes: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. It is guaranteed that no reallocation takes place during insertions that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the size specified in the most recent call to reserve().
