3 ms·
Something that is amortized complexity: vector.push(x) Most of the time, it's O(1). Sometimes it's O(n). If you double the size of the backing array when
by mcguire 6y ago
Something that is amortized complexity:
vector.push(x)
Most of the time, it's O(1). Sometimes it's O(n). If you double the size of the backing array when it runs out of space, it's amortized O(1).
- randomswede 6y agoOr triple, or quadruple. Or even (IIRC) "increase by 50%" (but, I would need to sit down and do the actual math on that). But, doubling a number is cheap and more conservative than quadrupling (the next "cheap" multiplier).