I am learning C++ and noticed that the running time for the push_back function for vectors is constant "amortized." The documentation further notes that "If a reallocation happens, the reallocation is itself up to linear in the entire size."
Shouldn't this mean the push_back function is $O(n)$, where $n$ is the length of the vector? After all, we are interested in worst case analysis, right?
I guess, crucially, I don't understand how the adjective "amortized" changes the running time.
The important word here is "amortized". Amortized analysis is an analysis technique that examines a sequence of $n$ operations. If the whole sequence runs in $T(n)$ time, then each operation in the sequence runs in $T(n)/n$. The idea is that while a few operations in the sequence might be costly, they can't happen often enough to weigh down the program. It's important to note that this is different from average case analysis over some input distribution or randomized analysis. Amortized analysis established a worst case bound for the performance of an algorithm irrespective of the inputs. It's most commonly used to analyse data structures, which have a persistent state throughout the program.
One of the most common examples given is the analysis of a stack with a multipop operations that pops $k$ elements. A naive analysis of multipop would say that in the worst case multipop must take $O(n)$ time since it might have to pop off all the elements of the stack. However, if you look at a sequence of operations, you'll notice that the number of pops can not exceed the number of pushes. Thus over any sequence of $n$ operations the number of pops can't exceed $O(n)$, and so multipop runs in $O(1)$ amortized time even though occasionally a single call might take more time.
Now how does this relate to C++ vectors? Vectors are implemented with arrays so to increase the size of a vector you must reallocate memory and copy the whole array over. Obviously we wouldn't want to do this very often. So if you perform a push_back operation and the vector needs to allocate more space, it will increase the size by a factor $m$. Now this takes more memory, which you may not use in full, but the next few push_back operations all run in constant time.
Now if we do the amortized analysis of the push_back operation (which I found here) we'll find that it runs in constant amortized time. Suppose you have $n$ items and your multiplication factor is $m$. Then the number of relocations is roughly $\log_m(n)$. The $i$th reallocation will cost proportional to $m^i$, about the size of the current array. Thus the total time for $n$ push back is $\sum_{i=1}^{\log_m(n)}m^i \approx \frac{nm}{m-1}$, since it's a geometric series. Divide this by $n$ operations and we get that each operation takes $\frac{m}{m-1}$, a constant. Lastly you have to be careful about choosing your factor $m$. If it's too close to $1$ then this constant gets too large for practical applications, but if $m$ is too large, say 2, then you start wasting a lot of memory. The ideal growth rate varies by application, but I think some implementations use $1.5$.
Although @Marc has given (what I think is) an excellent analysis, some people might prefer to consider things from a slightly different angle.
One is to consider a slightly different way of doing a reallocation. Instead of copying all the elements from the old storage to the new storage immediately, consider copying only one element at a time -- i.e., each time you do a push_back, it adds the new element to the new space, and copies exactly one existing element from the old space to the new space. Assuming a growth factor of 2, it's pretty obvious that when the new space is full, we'd have finished copying all the elements from the old space to the new space, and each push_back have been exactly constant time. At that point, we'd discard the old space, allocate a new block of memory that was twice as large again, and repeat the process.
Pretty clearly, we can continue this indefinitely (or as long as there's memory available, anyway) and every push_back would involve adding one new element and copying one old element.
A typical implementation still has exactly the same number of copies -- but instead of doing the copies one at a time, it copies all the existing elements at once. On one hand, you're right: that does mean that if you look at individual invocations of push_back, some of them will be substantially slower than others. If we look at a long term average, however, the amount of copying done per invocation of push_back remains constant, regardless of the size of the vector.
Although it's irrelevant to the computational complexity, I think it's worth pointing out why it's advantageous to do things as they do, instead of copying one element per push_back, so the time per push_back remains constant. There are are least three reasons to consider.
The first is simply memory availability. The old memory can be freed for other uses only after the copying is finished. If you only copied one item at a time, the old block of memory would remain allocated much longer. In fact, you'd have one old block and one new block allocated essentially all the time. If you decided on a growth factor smaller than two (which you usually want) you'd need even more memory allocated all the time.
Second, if you only copied one old element at a time, indexing into the array would be a little more tricky -- each indexing operation would need to figure out whether the element at the given index was currently in the old block of memory or the new one. That's not terribly complex by any means, but for an elementary operation like indexing into an array, almost any slow-down could be significant.
Third, by copying all at once, you take much better advantage of caching. Copying all at once, you can expect both the source and destination to be in the cache in most cases, so the cost of a cache miss is amortized over the number of elements that will fit in a cache line. If you copy one element at a time, you might easily have a cache miss for every element you copy. That only changes the constant factor, not the complexity, but it can still be fairly significant -- for a typical machine, you could easily expect a factor of 10 to 20.
It's probably also worth considering the other direction for a moment: if you were designing a system with real-time requirements, it might well make sense to copy only one element at a time instead of all at once. Although overall speed might (or might not) be lower, you'd still have a hard upper bound on the time taken for a single execution of push_back -- presuming you had a real-time allocator (though of course, many real-time systems simply prohibit dynamic allocation of memory at all, at least in portions with real-time requirements).
