Why does growing a buffer by a fixed 4096 slots per overflow make n appends quadratic?
answer
- count two things, not one
- how many growths, and how big each copy is
- the k-th growth copies k chunks
- adding up those copies gives a triangle
- constants cannot change the curve's shape
basics
~20 sA fixed chunk means one reallocation every 4096 appends, and each of those copies the entire prefix stored so far. Total copy work therefore grows with n squared. A bigger chunk lowers the constant but never changes the quadratic order.
solid answer
~50 sWith additive growth the number of reallocations is proportional to n: reaching n elements takes about `n/4096` of them. But the k-th reallocation copies about `k * 4096` elements, because it moves everything stored so far. Summing those copies gives roughly `n² / (2 * 4096)` element moves — quadratic in n, so a day's ingest of tens of millions of events spends most of its time copying. Raising the chunk to a million divides the constant by about 244 and wastes up to a million slots, but the curve is still a parabola. The fix has to change the *shape* of the rule, not its constant: make the new capacity a constant factor greater than the old, so each copy buys a number of free appends proportional to the work just done, which keeps the total copying linear.
code
pseudocode · 13 linesCHUNK = 4096
APPEND(buf, x):
if buf.size == buf.capacity:
newcap = buf.capacity + CHUNK // additive, not multiplicative
new = allocate(newcap)
for i in 0..buf.size-1: // copies everything stored so far
new[i] = buf.block[i]
release(buf.block)
buf.block = new
buf.capacity = newcap
buf.block[buf.size] = x
buf.size = buf.size + 1go deeper
Recall that each growth copies every element stored so far, not just the newly added chunk, and that the copy gets larger as the buffer gets larger.
Be ready to derive the total: about n/c growths, the k-th copying k·c elements, summing to roughly n²/(2c). Then say precisely why a multiplicative rule escapes it.
Show how you would recognise this in production — throughput decaying as a batch runs, profiles dominated by bulk memory movement — and confirm it by reading the growth rule rather than by guessing.
Frame it as a class of defect rather than a bug: growth policy is invisible in small tests, so it belongs in review checklists and load tests sized at production volume, not in post-incident analysis.
## The setup A log-ingest service appends event records into a growable buffer whose final length nobody knows in advance. Someone reasons: "doubling wastes memory; I'll grow by a comfortable fixed chunk of 4096 slots each time it fills." This feels prudent, and it is the single most expensive well-intentioned decision available in this corner of the subject. ## Counting the work honestly Two quantities matter, and conflating them is where the wrong answer comes from: 1. **How many reallocations happen.** 2. **How much each reallocation copies.** With an additive rule of chunk size `c`, the capacities go `c, 2c, 3c, 4c, ...`. To hold n elements you need about `n/c` reallocations — that count grows *linearly* with n. If you stop counting there, additive growth looks fine: only one expensive event per 4096 appends, or 0.02% of appends. But the k-th reallocation copies everything currently stored, which is `(k-1)c` elements. The total number of element copies over the life of the buffer is ``` c * (1 + 2 + 3 + ... + (m-1)) where m = n/c = c * m(m-1)/2 ~ n^2 / (2c) ``` That is Θ(n²). For n = 50 million events with c = 4096, the buffer performs about 12,000 reallocations, and the *average* one copies about 25 million elements. The total is on the order of 3 × 10¹¹ element moves — hours of memory bandwidth to build a list you could have built in seconds. ## Why a bigger chunk does not rescue it The natural next move is "fine, use a million-slot chunk." That divides the total by about 244 and it genuinely helps at moderate n — which is exactly why the bug survives code review and testing. But `n²/(2c)` is still quadratic: doubling the input still roughly quadruples the copying, and each growth still copies the whole prefix. You have bought yourself a bigger n before the curve bites, at the cost of up to a million idle slots and a bigger single stall on each growth. The chunk is a constant; constants do not change asymptotic shape. The same trap catches cleverer-looking sublinear rules. Growing by `sqrt(size)` slots reduces the reallocation count to about `2*sqrt(n)`, but the copies still sum to Θ(n^1.5) — better than quadratic, still superlinear, still wrong for an ingest path. ## What actually fixes it The rule has to be **multiplicative**: `new_capacity = factor * old_capacity` for some constant `factor > 1`. Then the free slots handed out by a copy are proportional to the number of elements just copied — copying k elements buys `(factor - 1) * k` free appends before the next copy. Each copy pays for the appends that follow it, so the copying work spread across a run of n appends stays proportional to n rather than to n². Two consequences fall out immediately: the number of reallocations to reach n is logarithmic rather than linear, and the amortized cost per append is constant. Note what the multiplicative rule does *not* promise. It does not make any individual append cheap — the growth appends still copy everything, and they get bigger as the buffer grows. It only bounds the total. ## The comparison in one table | Growth rule to reach n elements | Reallocations | Total elements copied | Amortized per append | |---|---|---|---| | +1 slot each time | ~n | Θ(n²) | Θ(n) | | +c slots each time (c constant) | ~n/c | Θ(n²/c), still Θ(n²) | Θ(n/c), still Θ(n) | | +sqrt(size) slots | ~2·sqrt(n) | Θ(n^1.5) | Θ(sqrt(n)) | | ×factor each time (factor > 1) | Θ(log n) | Θ(n) | Θ(1) | ## Diagnosing it in the wild Quadratic append is quiet in tests and loud in production, because it only shows at the input sizes tests do not reach. Symptoms: throughput that degrades steadily as a batch runs rather than staying flat; a profile dominated by bulk memory-move work rather than by your parsing or business logic; a job that takes four times as long when yesterday's volume doubled. The confirmation is arithmetic, not tooling — if you can find the growth rule and it adds rather than multiplies, you already know the answer. ## The wrong answer to avoid "Growing by a large fixed chunk is basically the same as doubling; it just tunes the tradeoff." It is not the same. It is a different complexity class, and the difference is invisible until the input gets large enough that it is expensive to discover.
- Would raising the chunk from 4096 to one million slots make the total linear?No. It divides the total copy work by about 244, which helps at moderate sizes, but the total is still proportional to n²/chunk — quadratic. You have also committed to up to a million idle slots and a larger stall on each growth. Only a multiplicative rule changes the order.
- What property must a growth rule have for appends to stay amortized constant?The new capacity must be a constant factor greater than one times the old, so the free slots gained are proportional to the elements just copied. Then each expensive copy pays for the cheap appends that follow it, and the number of growths to reach n is logarithmic rather than linear.
- Growing by the square root of the current size sounds like a compromise — is it?It is better than a fixed chunk but still wrong asymptotically. The number of growths drops to about two times the square root of n, yet the copies sum to n raised to the power 1.5. Superlinear total work means throughput still degrades as the buffer grows, just more slowly.
saying these in an interview costs you the question
- Says a large enough fixed chunk is asymptotically as good as doubling
- Counts only the number of reallocations, never each copy's length
- Claims copying is free because memory moves are fast
- Thinks quadratic behavior only appears at unrealistic sizes
- Believes any growth rule gives constant amortized append