What is the worst-case cost of a single append to a growable character buffer?
answer
- most appends just write into spare room
- what happens when there is no spare room?
- reallocation copies what is already there
- the total is a geometric series, not arithmetic
- amortized bounds a sequence, not one operation
basics
~20 sOne append is usually constant time, but the append that finds the buffer full is O(n): it allocates a larger block and copies every buffered character across. Amortized over many appends the total is still O(n).
solid answer
~40 sA growable character buffer writes into spare capacity, so almost every append is a single write plus a length update — constant time. When capacity runs out, that append must allocate a larger block and copy all n buffered characters into it, so its worst case is Θ(n). Because the buffer grows by a constant factor greater than one, the copy costs form a geometric series bounded by a constant times the final length, which is why the *amortized* cost per append is O(1) and n appends total O(n). The distinction matters in practice: amortized bounds the total over a worst-case sequence; it promises nothing about any individual operation. If you have a strict per-operation latency budget, size the buffer up front so the growth step never happens on the critical path.
go deeper
Know that a growable buffer keeps spare capacity, so appending normally just writes one character. Recall that when the capacity fills, the buffer must move to a bigger block and copy what it already holds.
Explain the mechanics: capacity versus length, reallocate-and-copy on overflow, growth by a constant factor making total copying a geometric series. State clearly that the worst single append is linear even though the amortized cost is constant.
Show where the rare linear append actually hurts — tail latency inside a request, and doubled peak memory while both blocks are live — and how you remove it: presize from a known or estimated final length rather than trusting the amortized bound.
Own the framing that amortized analysis is a throughput guarantee and percentile budgets need a different argument. Decide when a chunked or segment-based build, which never relocates data, is worth its extra complexity for your service's latency contract.
## What a growable buffer actually is A growable character buffer holds a mutable block of characters plus two numbers: the block's **capacity** and the **length** currently in use. Appending writes at index `length`, then increments `length`. That is a couple of instructions — genuinely constant time — and it is what happens on the overwhelming majority of appends. When `length == capacity` there is nowhere to write. The append must then: 1. allocate a new block with a larger capacity, 2. copy all `n` buffered characters into it, 3. release the old block, 4. finally perform the write it was asked to do. Step 2 is linear in what is already buffered. So the honest answer to "what does one append cost" is: **O(1) usually, Θ(n) on the growth step**. ## Why the total is still linear Suppose capacity grows by a constant factor greater than one each time it fills. Then the growth steps happen at capacities that form a geometric progression, and the characters copied across all growth steps are the sum of that progression. A geometric series whose ratio exceeds one is dominated by its *last* term: the sum is at most a constant multiple of the final capacity. So total copying across n appends is O(n), and dividing by n appends gives **O(1) amortized per append**. Contrast the alternative that people sometimes propose: grow by a fixed number of characters, say 64, each time. Then growth happens after every 64 appends, and the i-th growth copies about 64i characters. The total is 64(1 + 2 + ... + n/64), an arithmetic series again, and the whole build is Θ(n^2) — the exact quadratic you switched to a buffer to escape. The constant *factor* is not decoration; it is the reason the amortized bound exists. ## Amortized is not average-case This is where interviews separate answers. - **Amortized** analyses a worst-case *sequence* of operations and reports total cost divided by the number of operations. No probability is involved. "Amortized O(1) append" is a guarantee about any n consecutive appends: their total is O(n), always. - **Average-case** assumes a probability distribution over inputs and reports expected cost. Different tool, different claim. And critically, neither one says a *particular* operation is fast. The append that triggers growth on a buffer holding ten million characters copies ten million characters, and no amortized bound makes that append quick. It makes it *rare*, and it makes rarity pay for expense across the sequence. ## Why the distinction is not academic Two places it bites: **Tail latency.** If your per-request budget is measured at p99 or p999, an occasional linear copy inside a request is exactly the sort of thing that lands there. Amortized reasoning is a *throughput* argument; it does not defend a latency percentile. The remedy is to remove the growth step from the hot path: if you know or can estimate the final length, allocate that capacity when you create the buffer, and no growth ever occurs. **Peak memory.** During the copy, the old block and the new block are both live. Momentarily you hold more than the final size in memory. On a small buffer nobody notices; on a large document under a memory ceiling it can be the difference between fitting and not. ## If you truly cannot tolerate the copy When even the rare linear step is unacceptable — a hard real-time budget, or a document large enough that copying it stalls noticeably — you can build with a structure that never relocates data: keep a list of fixed-size chunks (or a rope-like tree of segments) and stitch them at the end. Every append then touches only the current chunk, so the worst single append is genuinely constant, and you pay instead with a more complicated read path and a final assembly pass. This is a deliberate trade of worst-case smoothness for average simplicity, and saying so out loud is the senior version of this answer. ## What to say in the room "Almost every append is constant time. The one that fills the buffer is linear, because it reallocates and copies. Growth by a constant factor makes the total copying a geometric series, so the amortized cost is constant — but amortized bounds a sequence, not an operation, and if I have a latency budget I presize instead of relying on it."
- You have a strict per-append latency budget. Is amortized O(1) good enough?No. Amortized bounds the total over a sequence; a single append can still stall for Θ(n) while the buffer is reallocated and copied. If the final length is known or estimable, allocate that capacity up front so growth never happens. If it truly is not, build into a list of fixed-size chunks so no append ever relocates existing data, and pay with a final assembly pass.
- What if the buffer grew by a fixed number of characters rather than by a constant factor?The amortized guarantee disappears. Fixed-increment growth reallocates every c appends, and the i-th reallocation copies about c*i characters, so total copying is an arithmetic series and the build becomes Θ(n^2). You would be back to the quadratic behaviour the buffer was supposed to eliminate, just with a smaller constant.
Moving to a bigger apartment when you outgrow the current one: most days you just put another box in the corner; on moving day you carry everything you own. Rare, but not cheap.
saying these in an interview costs you the question
- Says every append is O(1) because appends are amortized O(1)
- Uses amortized and average-case as synonyms
- Thinks growing the buffer copies only the new characters
- Believes fixed-increment growth still gives constant amortized cost
- Ignores that old and new blocks are both live during the copy