News for hackers. Stuff that matters.

A comment on It Can Happen to You. Parent comment

Re:It Can Happen to You by mcguire on Thursday March 04, 2021 @03:49PM (#26348076)
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).
[ Parent | on HN ]
Re:It Can Happen to You by randomswede on Friday March 05, 2021 @03:53AM (#26354531)
Or 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).
[ Parent | on HN ]