Why is building a String by repeatedly using += inside a loop slow, and how slow does it get as the number of iterations grows?
answer
- String is immutable → += copies everything each time
- 1+2+...+n = n^2/2 copies → O(n^2)
- StringBuilder = mutable buffer, append is amortized O(1) → O(n)
- Garbage: a new throwaway String per iteration
- Plain + outside a loop is fine
basics
~20 sStrings in Java can't be changed, so each += makes a brand-new String by copying all the characters so far plus the new ones. Doing that every loop turn means you copy more and more text, so the total work grows much faster than the number of loops.
solid answer
~40 sJava Strings are immutable, so += can't append in place; it creates a new String each time by copying the existing characters plus the new ones. On iteration i you copy roughly i characters, so summing over n iterations gives 1+2+...+n, which is about n^2/2 character copies — O(n^2) total work and lots of throwaway objects for the garbage collector. For small n it's invisible, but at thousands or millions of iterations it dominates runtime. The fix is StringBuilder, which keeps a growable char[] buffer and appends in amortized O(1), making the whole loop O(n). So inside loops use StringBuilder (or a stream collector / String.join); plain + outside loops is fine.
go deeper
Knows String is immutable and that += in a loop is slow, and reaches for StringBuilder. Can state 'a new string is created each time'.
Quantifies it as O(n^2) vs O(n), explains the re-copy of the whole accumulated array each iteration, and the extra GC pressure from throwaway objects.
Derives the n(n+1)/2 series, contrasts amortized O(1) append, and knows plain + outside loops (and single-expression concat) is fine and even compiler-optimized.
Frames it as an algorithmic-complexity smell to catch in review/profiling, weighs StringBuilder vs streams/String.join, and considers pre-sizing and allocation/GC impact at scale.
## The setup A **String** in Java is an object that holds a sequence of characters. The critical property is that it is **immutable**: once a String object exists, its contents can never be changed. There is no method that edits a String in place; every operation that 'changes' a String actually returns a *new* String object. The `+` operator on Strings is **concatenation** — gluing two strings together. `"ab" + "cd"` produces a new String `"abcd"`. The `+=` form (`s += x`) is just shorthand for `s = s + x`: it reassigns the variable `s` to point at a newly created String. ## What happens inside the loop Consider: ```java String s = ""; for (int i = 0; i < n; i++) { s += "x"; // s = s + "x"; } ``` Because String is immutable, on each iteration the JVM must: 1. Allocate a new character array big enough for the *current* length of `s` plus the new piece. 2. **Copy every character already in `s`** into that new array. 3. Copy the new piece on the end. 4. Wrap it in a new String object and point `s` at it. The old String becomes garbage. The key cost is step 2: it copies the *whole* accumulated string every time. ## Why that is O(n^2) Let's count character copies. On iteration `i`, the string already holds about `i` characters, so step 2 copies about `i` characters. Total copies over the whole loop: ``` 1 + 2 + 3 + ... + n = n(n+1)/2 ≈ n^2 / 2 ``` That sum (an arithmetic series) is proportional to **n^2** — we call this **O(n^2)**, or *quadratic*. 'O(...)' (Big-O) is a way of describing how the work grows as input size grows, ignoring constant factors. Quadratic means: double the iterations and you roughly *quadruple* the work. Concrete feel: 1,000 iterations ≈ 500,000 copies (fine). 1,000,000 iterations ≈ 500,000,000,000 copies — that can take many seconds or minutes, plus it churns out ~1,000,000 throwaway String objects and their backing arrays, hammering the **garbage collector** (the JVM subsystem that reclaims unused objects). ## The fix: StringBuilder `StringBuilder` is a *mutable* companion to String. It holds an internal, growable `char[]` buffer and a length. `append(...)` writes into the free space at the end — no full re-copy — so each append is **amortized O(1)** (occasionally the buffer is full and is grown by copying once, but spread across all appends the average cost per append is constant). The whole loop becomes **O(n)** (linear): ```java StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { sb.append("x"); } String result = sb.toString(); ``` You build the final String once, at the end, with `toString()`. ## When plain + is fine Outside a loop, a *fixed* number of concatenations like `"Hello, " + name + "!"` is totally fine — it's O(1) work and, as a bonus, since Java 9 the compiler turns a single concatenation expression into one efficient call (via the `StringConcatFactory`), so you don't even pay for intermediate Strings. The quadratic trap is specifically **repeated += across many loop iterations**, which the compiler cannot fuse because each iteration is a separate statement that reads the previous result.
- Roughly how many total character copies happen if you += a single char n times into an initially empty string?About n(n+1)/2 ≈ n^2/2 — the arithmetic series 1+2+...+n, because iteration i copies the ~i characters already accumulated.
- Why doesn't the compiler just rewrite the loop to use a StringBuilder for me?It can fuse the concatenations within a single expression/statement, but across loop iterations each += is a separate statement that reads the previous loop's result, so it can't safely merge them into one builder. You must do it yourself.
saying these in an interview costs you the question
- Saying += 'just appends to the existing string' — it cannot; String is immutable and a new object is created each time.
- Claiming the JIT/compiler optimizes the loop into a StringBuilder automatically — it does NOT fuse concatenation across separate loop iterations.
- Confusing O(n^2) with O(n): the slowdown is the re-copy of the whole accumulated string, not just the new piece.
- Thinking the cost is only allocation; the dominant cost is copying all prior characters every iteration.