Why is string concatenation in a loop slow
String concatenation in a loop is slow because immutable strings are copied in full on every append, which makes the total work quadratic. Here is the arithmetic, how Python, Java, JavaScript and Go differ, and the fix.
String concatenation in a loop is slow because strings are immutable in most languages: every += allocates a new string and copies all the earlier characters into it. Appending n pieces copies about n²/2 characters in total, so the cost is quadratic. Collect the pieces in a list or builder and join once, which is linear.
What actually happens when you append to a string in a loop?
Each append creates a brand new string whose length is the old length plus the new piece, and the old contents are copied across before the new piece is added. Nothing is extended in place, because an immutable string promises that nobody else holding a reference will ever see it change.
Here is the loop most people write without thinking:
result = ""
for i in range(n):
result += "x"
Trace it. On iteration 1 the string has length 0, so we copy 0 characters and write 1. On iteration 2 we copy 1 and write 1. On iteration k we copy k-1 characters. The total number of characters copied is 0 + 1 + 2 + ... + (n-1), which equals n(n-1)/2. That is Θ(n²), even though the loop body looks like a single constant-time statement.
This is the general lesson I keep returning to: a line that looks O(1) is only O(1) if the operation it hides is O(1). I wrote about that gap between how code reads and what it costs in Complexity is a contract, not a fact. String append is one of the cleanest examples, because the contract of the operation (return a new value) forces the copy.
An analogy that helps me: imagine a bound book where you are not allowed to add a page. To add one sentence, you must reprint the entire book with the sentence at the end, then throw the old copy away. A hundred sentences means a hundred full reprints, and each reprint is longer than the last. The sane alternative is a loose-leaf stack: drop each page on the pile as it arrives, and bind the book exactly once at the end. A list followed by join, or a string builder, is the loose-leaf stack.
How much slower is it with real numbers?
It is slower by a factor that grows with n, and at a few hundred thousand appends the gap is the difference between milliseconds and seconds. The arithmetic is easy enough to do on paper, so let us do it.
Suppose you build a string of n single-character appends. The naive approach copies n(n-1)/2 characters in total. A builder with a doubling buffer copies far less: whenever the buffer fills, it allocates twice the capacity and copies the current contents. The copies happen at sizes 1, 2, 4, 8, and so on up to n, so the total is at most 1 + 2 + 4 + ... + n, which is under 2n. Add the n writes themselves and the builder performs fewer than 3n character operations.
Plug in four sizes:
- n = 1,000: naive copies about 500,000 characters; builder about 3,000. Both finish in well under a millisecond. Nobody notices.
- n = 10,000: naive copies about 50 million characters; builder about 30,000. The naive version is now a few milliseconds of memory traffic, still easy to miss.
- n = 100,000: naive copies about 5 billion characters; builder about 300,000. At a sustained memory copy rate somewhere around 5 to 10 GB/s, 5 billion bytes is roughly half a second to a second, before counting the cost of allocating and freeing 100,000 progressively larger blocks. The builder takes about a millisecond.
- n = 1,000,000: naive copies about 500 billion characters, which is on the order of a minute or more. The builder still takes a few milliseconds.
Those timings are back-of-envelope estimates from the copy volume, not benchmark results, and real numbers will shift with your allocator, cache sizes and character width. What does not shift is the ratio. Going from 100,000 to 1,000,000 appends multiplies the naive cost by 100 and the builder cost by 10. That 10x versus 100x growth is the whole story, and it is why this bug passes every small test and then fails the large one. If you have seen a solution pass 9 of 10 test cases and then time out, this is one of the usual suspects; I go through the rest of that checklist in Why does my solution get time limit exceeded?
Note also that the pieces do not have to be single characters. If you append n pieces of average length m, the final length is nm and the naive copy volume is about m·n²/2. Longer pieces make it worse, not better.
Why does string concatenation sometimes seem fast anyway?
Because some runtimes quietly rescue you, and some small inputs never expose the problem. Neither is a guarantee you should build on.
CPython has an optimisation for s += t when the string s has exactly one reference. In that case the interpreter can resize the existing buffer with realloc, which often extends in place and makes the loop behave close to linear. But this is an implementation detail of one interpreter. It stops working the moment a second reference to the string exists (say, you stored it in a dict or another variable), and it does not exist in PyPy or other implementations. The language documentation recommends "".join precisely because the in-place trick is not part of the contract.
JavaScript engines such as V8 represent the result of a + b as a rope (a tree node pointing at both halves) instead of copying immediately. Appends are cheap, and the tree is flattened into a contiguous string only when something needs it, such as indexing or a regex. So += in a loop is usually fine in JavaScript, and many style guides there prefer it. The cost moves rather than vanishes: flattening is a linear pass, and code that alternates appending with reading characters can trigger repeated flattening.
Java is the instructive case. The compiler rewrites a single a + b + c expression into a StringBuilder chain, which leads people to think concatenation is always optimised. But inside a loop, s += x creates a fresh builder on every iteration, copies s into it, appends, and produces a new String. The loop is still quadratic. Go and C# behave the same way: strings are immutable, and += in a loop copies each time.
The other reason it seems fast is small n. If you are joining five words, the quadratic term is 10 character-copies of a few bytes each. Do not rewrite that. The rule is not that concatenation is evil; the rule is that it is a linear operation, and a linear operation inside a loop of n iterations is quadratic.
What should you use instead of string concatenation in a loop?
Use whatever your language provides for accumulating pieces and materialising the string once: a list plus join in Python, StringBuilder in Java and C#, strings.Builder in Go, and push_back or += on a mutable std::string in C++. Here are the usual forms:
# Python
parts = []
for i in range(n):
parts.append("x")
result = "".join(parts)
// Java
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append('x');
}
String result = sb.toString();
// Go
var sb strings.Builder
for i := 0; i < n; i++ {
sb.WriteByte('x')
}
result := sb.String()
The trade-offs between the approaches:
| Approach | Characters copied for n appends | Time | Notes |
|---|---|---|---|
Naive += on immutable strings | about n²/2 | O(n²) | Fine for under roughly 100 pieces; Java, Go, C# always pay it |
CPython += with one reference | often near n | usually O(n) | Implementation detail; breaks with aliasing and on other interpreters |
List then join | n (one final copy) | O(n) | Needs memory for the list of pieces as well as the result |
| StringBuilder / strings.Builder | under 2n (doubling buffer) | O(n) amortised | Best when you append repeatedly and read once |
| Rope (V8 style) | deferred until flatten | O(1) per append, O(n) flatten | Surprising cost if you index between appends |
| Preallocated char array | n (writes only) | O(n) | Needs the final length known; common in interview solutions |
The same amortised argument behind the builder is the one that makes dynamic arrays work, and it is the reason contiguous growth beats node-by-node growth in practice. If that reasoning is new to you, Why arrays beat linked lists in practice covers the cache and allocation side of it.
Which other patterns hide the same quadratic cost?
Any operation that copies a string, slice or array inside a loop carries the same trap, and the concatenation operator is only the most visible form. Learn to recognise the family, because interviewers lean on it.
- Repeated slicing. A loop that does
s = s[1:]to consume a string one character at a time copies the remainder every iteration. Total copy: n²/2 again. Use an index instead. - Recursion that passes substrings. A recursive palindrome check that calls itself on
s[1:-1]copies about n characters at the top level, n-2 at the next, and so on. The recursion depth is n/2, and the copy volume is about n²/4. Pass two indices and the copying disappears. - Prepending.
s = c + sis the same as appending, with the same cost. In an array, inserting at the front shifts all n elements, which is the same quadratic shape in a different costume. - Building keys in a loop. Constructing a string key for each of n states, where each key is length n, costs n² before the hash map even gets involved. Hashing a string is also linear in its length, so long keys make every lookup cost O(length), not O(1). I covered that angle in Why is my hash map slow?
- Joining inside a nested loop. Calling
"".joinon a growing list once per iteration re-pays the full linear cost each time. Join once, after the loop.
In each case the repair has the same shape: stop producing intermediate values nobody asked for. Keep indices, keep a mutable buffer, and produce the final string exactly once.
How should you talk about this in a coding interview?
State the cost out loud and fix it before the interviewer asks. A sentence like "appending to an immutable string copies it, so this loop is O(n²); I will collect characters in a list and join at the end for O(n)" shows exactly the awareness the question is probing for.
Consider a typical task: reverse the words in a sentence of 200,000 characters. The tempting solution walks the input and builds the answer with result = word + " " + result. With roughly 40,000 words of average length 5, each prepend copies the whole result so far. The average result length is about 100,000 characters, and there are 40,000 prepends, so you copy around 4 billion characters. The better solution splits into a list of 40,000 words, reverses the list in 40,000 steps, and joins once for a copy of 200,000 characters. Same output, a 20,000-fold difference in copy volume. The difference between those two answers is rarely about cleverness; it is about knowing what the operator costs.
A few habits make this automatic:
- Whenever you write a string operator inside a loop, ask whether it is O(1) or O(length). Say the answer in your head.
- If the answer is O(length), multiply by the number of iterations. If the product is above about 10⁸ for the stated limits, change the approach.
- Prefer indices over substrings when scanning, and prefer one buffer over many intermediate strings when building.
- When you have to compare many substrings, consider whether a rolling hash or a prefix structure would avoid creating them at all.
None of this is exotic. It is bookkeeping about where the copies happen, and it pays off far more often than any micro-optimisation of the loop body.
Frequently asked questions
Is string concatenation in a loop always O(n²)?
No. It is quadratic when each append copies the existing string, which is the case for Java, Go and C# and for CPython when the string is aliased. Runtimes with in-place resizing or ropes can make it close to linear, but those are implementation details, so portable code should use a builder or join.
Is a list plus join really faster than +=, or only in theory?
It is faster in practice once the number of pieces reaches the thousands, and dramatically so at the hundred-thousand scale where naive copying moves billions of characters. For fewer than about a hundred short pieces the difference is unmeasurable, so choose whichever reads better.
What should I practise next to avoid hidden quadratic costs?
Work through string problems where you must track a window or a pair of indices instead of building substrings, and for each one write down the cost of every operation inside the loop. A good place to start is the strings topic page.