Why does growing a buffer by a fixed 1,000 slots instead of doubling cost Theta(n^2) overall?
answer
- how often does a resize fire now?
- resizes every 1,000 appends, forever
- the copy sizes keep growing but the gaps do not
- 1000 + 2000 + 3000 + ... + n
- an arithmetic series is quadratic
basics
~20 sA fixed step makes resizes fire at a constant rate forever while each copies more elements, so copy sizes form the arithmetic series 1000+2000+...+n. That sums to about n squared over 2000, and per-append cost grows with n.
solid answer
~50 sDoubling works because resizes get exponentially rarer as they get more expensive. A fixed additive step kills the first half of that bargain: with a 1,000-slot step you resize every 1,000 appends no matter how big the buffer is, and each resize copies everything already there. The copy sizes form an arithmetic series `1000 + 2000 + ... + n`, which sums to roughly `n^2 / 2000` — quadratic, not linear. Concretely, at one million readings that is about 500 million element copies versus about two million for doubling, and the average per-append copy cost is around 500 elements rather than a constant. The tell is that the per-append cost keeps rising: double the input and the average per-append work doubles too. The usual motivation, that doubling wastes memory, is also weaker than it sounds, since doubling caps idle capacity at half the buffer.
go deeper
Recall that a resize copies the whole buffer, not just the new slots. If growth adds a fixed number of slots, resizes never become rarer, and that is the sentence the interviewer is listening for.
Derive the total on the spot: copy sizes k, 2k, ..., n form an arithmetic series summing to about n squared over 2k. Be ready to say that the step divides the quadratic term but does not remove it.
Show what this looks like in production: throughput that decays with data volume, resize pauses that are both frequent and lengthening, and a load test that passes because it stopped two orders of magnitude short of the real ceiling.
Own the framing that additive growth is a bet on a bounded final size and multiplicative growth a bet on an unbounded one. Be able to say when the tighter memory bound is genuinely worth a quadratic copy term, and when it is not.
## The proposal, and why it sounds reasonable An ingestion buffer collecting sensor readings grows by doubling, and someone points out that a buffer holding a million readings may have allocated space for two million. The suggested fix: stop doubling, grow by a fixed 1,000 slots each time the buffer fills. Waste is then bounded by 1,000 slots instead of by half the buffer, which sounds strictly better on memory. The reason it is not is that it changes the *asymptotics of the copying*, and asymptotic copy work beats a constant memory factor long before a real workload gets interesting. ## Deriving the total With a fixed step `k`, the buffer fills and resizes when the count reaches `k`, `2k`, `3k`, ... up to `n`. Each resize copies everything present, so the copy sizes are `k`, `2k`, `3k`, ..., `n`. That is an arithmetic series, and an arithmetic series is quadratic in its length: `k + 2k + 3k + ... + n = k * (1 + 2 + ... + n/k) = k * (n/k)(n/k + 1)/2 ~ n^2 / (2k)` So the total copy work is `Theta(n^2 / k)`. The constant `k` divides the quadratic term; it does not remove it. That is the single most important line of the derivation, and the one candidates most often fumble: choosing a bigger step (10,000, 100,000) shifts the curve down but leaves it a parabola. ## The arithmetic on a real buffer Take `n = 1,000,000` readings and `k = 1,000`: | policy | resizes | total element copies | average copies per append | |---|---|---|---| | grow by 1,000 | about 1,000 | about 500,000,000 | about 500 | | double | about 20 | under 2,000,000 | under 2 | Roughly 250 times more copy work, and the gap widens with `n`. The per-append average is `n / (2k)` — it grows *linearly with the buffer size*. At two million readings each append averages about 1,000 element copies; at ten million, about 5,000. There is no size at which the policy settles down. ## What the on-call engineer sees This failure has a recognisable shape in production. Throughput does not fall off a cliff; it decays. The ingestion rate looks fine in a load test that runs to a hundred thousand readings and unacceptable at ten million, because the constant-looking per-append cost was actually a linear function of buffer size all along. A latency graph shows resize pauses that are both *frequent* (every 1,000 appends, forever) and *steadily lengthening*, so the mean climbs as well as the tail. Contrast that with doubling, where the pauses are rare and the mean is flat even though individual pauses get bigger. ## Why the memory argument was weaker than it looked Doubling never wastes more than half the allocated slots, and only momentarily after a growth; the overhead is a bounded fraction, not an unbounded leak. Trading a bounded constant-factor memory overhead for a quadratic time term is a bad trade for any buffer whose size is not known to stay small. ## When a fixed step is actually fine The quadratic term only bites once `n/k` — the number of resizes — becomes large. If a buffer provably tops out at a few multiples of `k` (a per-request scratch buffer, a fixed-size window of readings, a fixed-length record header), a fixed step performs a handful of copies over its lifetime and the memory economy is real. The honest formulation is: *additive growth is a choice about a bounded `n`, multiplicative growth is a choice about an unbounded one.* An engineer who says "fixed step, because this buffer never exceeds five thousand entries and I would rather not hold ten thousand slots" has made a defensible call. An engineer who says "fixed step because doubling is wasteful" for an open-ended ingestion buffer has not. ## The general principle to carry away What makes append amortized constant is not the number 2 — it is that capacity is multiplied by a factor greater than one, so the interval between resizes grows in proportion to the work each resize does. Any policy that preserves that proportionality gives a linear total; any policy that fixes the interval while letting the work grow gives a quadratic one. The same test applies to any structure that rebuilds itself when it fills.
- Would raising the step from 1,000 to 100,000 fix it?No. The total is `n^2 / (2k)`, so a bigger `k` divides the quadratic term by a hundred but leaves it quadratic. It buys you a factor, not a different growth curve, and at ten times the data the extra factor is gone again. It also raises the fixed memory overhead, which was the original motivation for the change.
- How much copy work is a million readings under each policy?About 500 million element copies with a 1,000-slot step — roughly a thousand resizes copying an average of half a million elements each — against under two million copies with doubling, where about twenty resizes fire in total. That is a factor of roughly 250, and it grows as the buffer does.
- Is a fixed step ever the right choice?Yes, when the final size is genuinely bounded and small relative to the step. A scratch buffer that never exceeds a few multiples of the step does only a handful of copies in its lifetime, and the tighter memory bound is real. The quadratic term only matters once the number of resizes gets large.
It is like repacking your entire van every time you add one more box past a fixed thousand. The repacks never get rarer, and each one moves everything already loaded.
saying these in an interview costs you the question
- Says a fixed step is fine because resizes are still rare
- Thinks each resize copies only the 1,000 newly added slots
- Claims the constant 1,000 removes the n squared term
- Confuses the number of resizes with the work per resize
- Argues doubling wastes unbounded memory so additive is safer