Amortized analysis averages cost over a sequence of operations. std::vector::push_back is usually O(1) but occasionally O(n) when capacity doubles and elements copy—still O(1) amortized per push.
Intuition
- Rare expensive resize pays for many cheap appends
- Dynamic arrays double capacity → total copy work O(n) over n inserts
- Hash table rehash — occasional O(n), average insert still O(1) amortized
Contrast with worst case
Interview clarity: state amortized for vector push_back; state worst-case O(n) for a single insert if resize happens that call.
Simulate growth
#include
#include
int main() {
std::vector v;
v.reserve(2);
for (int i = 0; i < 6; ++i) {
v.push_back(i);
std::cout << "size=" << v.size() << " cap=" << v.capacity() << "\n";
}
return 0;
} Important interview questions and answers
- Q: Amortized O(1) meaning?
A: Average cost per operation over many ops stays constant even if some ops are expensive. - Q: Why double capacity?
A: Geometric growth keeps total copying O(n) for n appends.
Self-check
- Explain amortized analysis in one sentence.
- Why does vector capacity jump in steps?
Tip: push_back is amortized O(1)—mention rare resize when asked for precision.
Interview prep
- Amortized meaning?
Average cost per op over sequence—vector push_back O(1) amortized.
- Double capacity?
Keeps total copying O(n) over n inserts.