How is the time complexity of inserting an element at the end of a standard vector in C++ determined?

The amortized time complexity of inserting an element at the end of a standard vector (std::vector) in C++ is usually constant, i.e., O(1) on average. This is because the vector allocates extra memory, and when adding an element, if the current buffer is not full, the insertion is quick — the element is simply copied or moved.

However, when the internal buffer of the vector is full, a memory reallocation occurs: a new buffer of larger size (usually twice as large) is allocated, all elements are copied or moved to the new buffer, and the old one is freed. This operation takes O(n) time, where n is the current number of elements.

But since such reallocations do not happen at every insertion, but only periodically, the amortized complexity of inserting at the end remains O(1).

Example:

std::vector<int> v;
for (int i = 0; i < 1000; ++i) {
    v.push_back(i); // amortized O(1)
}