Why does building a string by repeated concatenation in a loop cost O(n^2) in total?
answer
- count the work, not the statements
- immutable means nothing is edited in place
- what must each step copy?
- the accumulated result grows every iteration
- 1 + 2 + ... + n is an arithmetic series
basics
~20 sEach concatenation on an immutable string allocates a brand-new string and copies every character accumulated so far. Copying 1 + 2 + ... + n characters sums to about n^2/2, so the loop is quadratic, not linear.
solid answer
~50 sAn immutable string cannot be extended in place, so `result = result + fragment` allocates a fresh string and copies both operands into it. After i iterations the accumulated result is i fragments long, and iteration i+1 copies all of it again. Total character copies are proportional to 1 + 2 + ... + n = n(n+1)/2, so the build is O(n^2) in the number of fragments — more precisely O(n * m), where m is the final length. The loop *looks* linear because it runs n times; the cost hides inside the assignment, not in the loop header. The fix is to append into a growable character buffer, or make a single join pass, so each character is copied a constant number of times and the build is O(m). On a 500,000-row report export that is the difference between a job that finishes and one that looks hung.
code
pseudocode · 7 linesresult = "" // immutable: cannot be extended in place
for i in 0..n-1
// allocates a new string of length
// length(result) + length(rows[i])
// and copies BOTH operands into it
result = concat(result, rows[i])
return resultgo deeper
Be ready to say why an immutable string cannot be extended, and that each concatenation copies everything built so far. Naming the arithmetic series 1 + 2 + ... + n and landing on O(n^2) is the whole answer at this level.
Explain where the cost hides: the loop body is one statement but its work grows each iteration. Express the bound both ways — O(n^2) in fragment count, O(n*m) in output length — and describe the allocation churn the loop also creates.
Show how you would catch this in a real system: what the profile looks like (allocation pressure rather than a hot loop), how you confirm quadratic scaling by measuring at two input sizes, and why the fix is linear rather than a constant-factor tune.
Own the generalisation: this shape recurs on any immutable sequence, so the lesson your team should carry is 'count the work per step, not the steps'. Decide whether it is worth a lint rule, a review checklist item, or a load test that would have caught it.
## The setup You are exporting a report: 500,000 rows, each formatted into a short line, all assembled into one document. The obvious code accumulates into a string: ``` result = "" for each row: result = result + format(row) ``` This is correct and it is quadratic. It is probably the single most common accidental O(n^2) in production code. ## Why immutability forces a copy An immutable string is a fixed block of characters that nobody may modify after creation. Concatenation therefore cannot append; it must **produce a new string**. Producing it means allocating a block big enough for both operands and copying both into it. That single concatenation of a string of length `a` with one of length `b` is O(a + b) — perfectly reasonable on its own, and *not* quadratic. A single concatenation is never the problem. The problem is doing it inside a loop where one operand keeps growing. ## The derivation Let the n fragments each have length k, so the final document has length m = n*k. Trace the accumulated length: | iteration | length copied | |---|---| | 1 | k | | 2 | 2k | | 3 | 3k | | ... | ... | | n | nk | Total characters copied = k(1 + 2 + ... + n) = k * n(n+1)/2 ≈ m*n/2. That is an arithmetic series, and arithmetic series are quadratic. Written in the fragment count it is O(n^2); written in terms of the output size it is O(n*m). Either way, doubling the number of rows quadruples the work. The 500,000-row export does roughly 125 billion character copies to produce a document of a few tens of megabytes. The secondary damage is allocation: the loop also creates n throwaway strings whose combined size is the same ~m*n/2 characters, so the allocator and whatever reclaims memory are both hammered. In a profile this often shows up as "memory pressure" rather than as the loop itself, which is why people misdiagnose it. ## Where the cost hides The reason this trap survives code review is that the loop body reads as one statement. Complexity intuition trained on "count the statements, multiply by the iterations" gives O(n). The correct habit is **count the work, not the statements**: ask what each statement copies, and whether that amount grows across iterations. Here it grows linearly, and linear work repeated n times is quadratic. ## The two fixes **Growable character buffer.** Append fragments into a mutable buffer that grows by a constant factor when it fills. Each character is written once and moved only during the occasional growth step, which totals O(m) across the whole build. One final conversion produces the immutable result. Total: O(m). **Single join pass.** If all fragments are already in hand, walk them once, allocate one block of exactly the total length, and copy each fragment into its slot. Two passes over the fragment list, one copy of each character, one allocation. Also O(m), and with the smallest possible peak memory. Both turn the 500,000-row export from quadratic into linear. The choice between them is a memory-and-allocation question, not a complexity question — asymptotically they are the same. ## A word on ecosystems This trap is a property of *immutable* strings, not of concatenation as such. Strings are immutable in Java, Python and JavaScript alike, so the loop above is quadratic in all three; C++ gives you a mutable string type that appends in place with amortized constant cost, so the same shape is linear there. Knowing which kind of string type you are holding tells you whether the loop is a bug. ## What an interviewer is listening for The derivation, stated out loud: immutable means a copy per step, the copied amount grows by one fragment each step, the sum of an arithmetic series is quadratic. Candidates who only recite "use a builder instead" have memorised the fix without the reason, and they will miss the same shape when it appears on lists, arrays or byte buffers — which it does, for exactly the same reason.
- The loop runs n times and each statement looks constant — where exactly does the quadratic cost hide?Inside the assignment. The concatenation allocates a new string and copies the entire accumulated prefix plus the new fragment, so the work per iteration is proportional to how much has already been built. Linear work performed n times is quadratic. The loop header is innocent; the operator in the body is not.
- Does the same trap appear when you build up a list or an array by repeated concatenation?Yes. The shape is about immutable sequences, not about text. Concatenating an immutable list to itself in a loop copies the accumulated prefix every time, giving the same arithmetic series and the same O(n^2). The fix is identical: append into a growable structure, or make one pass that allocates the final size and fills it.
- A reviewer says it runs fine on the 1,000-row test file. How do you argue it will fail at 500,000?Quadratic scaling: 500 times the rows is roughly 250,000 times the copying. Rather than arguing asymptotics, measure at two sizes an order of magnitude apart and show the ratio — if ten times the input takes about a hundred times as long, the curve is quadratic and extrapolation is arithmetic, not speculation.
Photocopying a growing stack of paper: to add one page you re-copy the whole stack. The last page is cheap to write and ruinously expensive to file.
saying these in an interview costs you the question
- Says each concatenation is a single constant-time operation
- Concludes the loop is O(n) because it runs n times
- Knows to use a buffer but cannot derive why the naive loop is quadratic
- Claims any concatenation is quadratic, even a single one
- Blames function-call overhead rather than the repeated copying