Strings Are Immutable. That's Why Concatenation in a Loop Is O(n²).

You've written this. Everyone has.

result = ""
for line in lines:
    result += line + "\n"

It looks harmless. On 100 lines, it is. On 100,000 lines, it's slow for a reason most engineers can't articulate. Your profiler knows. It's just been waiting for the right moment.

String concatenation in a loop is O(n²) because strings are immutable. Those two facts are directly linked. Understanding why requires understanding what immutability actually does in memory, and once you see it, you can't unsee it.

---

Elmo World.bas: one string, built character by character, in a loop, with GoTo. Peak string concatenation. This article exists so you never do this in Python.

---

What "Immutable" Actually Means in Memory

Immutable doesn't just mean "the variable is read-only." It means the object in memory cannot change. Ever.

When you write:

s = "hello"
s += " world"

Here is exactly what happens. "hello" is allocated at some address, call it 0x1000. " world" is allocated at 0x1010. A brand new string "hello world" is created at 0x1020, by copying all of "hello" and all of " world" into fresh memory. Then s is updated to point to 0x1020.

The original "hello" at 0x1000 is untouched. Nothing was appended to it. You made a copy and moved the pointer. The old string just sits there, waiting for garbage collection, entirely unaware of what just happened to it.

Two originals, one copy, one redirected pointer. The variable changes. The string does not.

This is fundamentally different from what a list does. my_list.append(x) modifies the list in place. my_string += x creates a new string and redirects the variable. The variable changes. The string does not.

Java makes this contractual: String is a final class and its internal byte array is private with no mutation methods. Python's str type exposes no mutation method. JavaScript strings are primitive values. The Go specification literally says "Strings are immutable." Ruby, Swift, Kotlin, C#: all the same. This was a deliberate, reasoned choice.

---

Immutability Wasn't Accidental

Interning: One Copy Per Identical Value

If a string object can never change, two variables can safely point to the same memory without either one being able to corrupt the other. The runtime can maintain a string pool, and every time you create a string literal, the runtime checks whether that exact content already exists. If it does, you get a reference back to the existing object. No duplication.

Java's JVM does this for all string literals. The string "hello" appears exactly once in the pool regardless of how many variables hold it. Python's CPython interns strings automatically when they look like identifiers (alphanumeric with underscores, under 4096 characters in recent versions). You can force it with sys.intern() for values that will be compared repeatedly.

This deduplication only works because immutable strings can be shared safely. If any piece of code could modify a shared "hello", every variable holding that string would silently become something else. Mutable strings make sharing unsafe. Immutable strings make it free.

Hash Caching: Compute Once, Look Up Forever

Strings are the most common dictionary key in existence. Hashing a string requires reading every byte. For a 500-character string, that's 500 operations per lookup.

Since an immutable string's content never changes, its hash never changes either. Java's String.hashCode() computes the hash on first call, stores it in a field on the String object, and returns the cached integer on every subsequent call. Python does the same. The first time you use a string as a dictionary key, the hash gets computed and stored. Every lookup after that is a single integer comparison.

If strings were mutable, any modification would invalidate the cached hash. You'd either recompute on every lookup (expensive), or you'd get silent bugs when a key string is modified after insertion (catastrophic). Immutability makes hash caching trivially correct by making cache invalidation impossible.

You can see this directly in Python:

s = "example"
hash(s)   # computed, stored internally
hash(s)   # returned from cache instantly

This is also why mutable objects (lists, dicts) can't be dictionary keys in Python: their hash would change if their contents changed, breaking the hash map invariant. See how hash maps use this for the full picture.

Thread Safety, No Lock Required

An immutable value can be shared across any number of threads with zero synchronization overhead. No mutex, no atomic reference, no memory barrier. Multiple threads reading the same string are just pointers to the same bytes.

Strings end up in shared state constantly: config values, HTTP headers, log format templates, database query strings. Making them immutable means all of that sharing is free, safe, and requires no thought. Mutable strings would require a lock every time a string crosses a thread boundary. Nobody wants to write that. Nobody wants to debug it either.

Security: The Value You Checked Is the Value You Use

If you pass a filename string to a function that first checks whether the user has permission, then opens the file, a mutable string opens a race condition. A second thread could modify the filename between the permission check and the open, redirecting the file access to something that never got checked. This is a TOCTOU (time-of-check-to-time-of-use) attack.

With immutable strings, the string you checked is physically the same bytes as the string you open. No thread can change it in between. The attack surface disappears because the bytes can't move.

---

Why String Concatenation in a Loop Is O(n²)

Now the bad news. If every concatenation creates a new string, then building a string piece by piece in a loop pays copy costs that grow with the current length of the result, not with the new piece being added.

Trace through building a string from n pieces, each of length k:

• Iteration 1: allocate a string of length k, copy k chars. Cost: k.
• Iteration 2: allocate a string of length 2k, copy 2k chars. Cost: 2k.
• Iteration 3: allocate a string of length 3k, copy 3k chars. Cost: 3k.
• ...
• Iteration i: copy ik chars. Cost: ik.

Total characters copied:

k·1 + k·2 + k·3 + ... + k·n  =  k · (1 + 2 + ... + n)  =  k · n(n+1)/2

Drop the constant: O(n²).

Each bar is one iteration. The total shaded area grows as n². One loop. Quadratic work. Nobody puts this in the code review.

You're doing n iterations, but you're copying O(n²) characters in total. The Python function at the top is secretly doing as much work as a nested loop. That's the punchline. One loop, quadratic work.

To put numbers on it: at n = 1,000, you copy roughly 500,000 characters. At n = 10,000, about 50 million. At n = 100,000, about 5 billion. That's why it seems fine in tests and then collapses in production.

---

The Fix: Collect Into a Buffer, Finalize Once

The solution is to stop materializing a string at each step. Collect pieces into a mutable buffer, then assemble exactly once at the end.

Python: use join()

# Bad: O(n²) copies
result = ""
for line in lines:
    result += line + "\n"

# Good: O(n) copies
result = "\n".join(lines)

str.join() does two passes: one to compute the total required length, one to copy each piece in. It allocates exactly one string of the right size. Total copies: proportional to the total content length, not quadratic.

When you need conditional logic, collect into a list first:

parts = []
for line in lines:
    if should_include(line):
        parts.append(process(line))
result = "\n".join(parts)

List append is amortized O(1), the same dynamic array trick that StringBuilder uses. See how dynamic arrays get there for the proof.

Java: use StringBuilder

// Bad: O(n²)
String result = "";
for (String word : words) {
    result += word + "\n";
}

// Good: O(n)
StringBuilder sb = new StringBuilder();
for (String word : words) {
    sb.append(word).append('\n');
}
String result = sb.toString();

StringBuilder maintains a private char[]. Each append() writes characters into the next available slot. When the array is full, it allocates a new array twice as large and copies the existing content. Across n appends, the doubling means total copy work is O(n) even counting all resize events. Each append is O(1) amortized. The final toString() copies once into an immutable String and you're done.

When capacity is hit, double the array, copy once, keep going. The doubling means total copy work stays O(n) across all resizes.

Go uses strings.Builder, C# uses System.Text.StringBuilder, and they work the same way. Rust's String type is already the mutable buffer (with &str as the immutable view), so you just push_str() in a loop directly.

The pattern is always: mutable buffer for accumulation, immutable string as the final result. It's not clever. It's just correct.

---

The Exceptions (and Why They Don't Change the Rule)

Java's compiler has been smart about + outside of loops since Java 5. This:

String s = "Hello, " + name + "!";

gets compiled to a single StringBuilder operation. Java 9 made this even more efficient using invokedynamic and StringConcatFactory. So at least one of us is thinking about this automatically. But neither change applies to += inside a loop. The compiler sees each loop iteration as independent. The quadratic behavior stands.

CPython has a specific optimization: if a string's reference count is exactly 1, meaning only one variable holds it, += can sometimes extend the underlying buffer in place instead of copying. This makes naive Python loops faster than the strict model predicts. It's why some Python benchmarks don't show the full quadratic blowup at moderate n.

But this is an implementation detail of one interpreter, not a language guarantee. It breaks the moment you pass the string into a function, store it in a container, or use a non-CPython runtime like PyPy or Jython. You cannot rely on it. CPython saving you occasionally is not a reason to skip join.

The rule stays simple: if you're building a string in a loop, use the right tool. The optimization that sometimes saves you is not a reason to skip the correct approach.

For string building outside loops, use whatever reads most clearly. Python f-strings (f"Hello, {name}") compile to efficient code that avoids the issue. Java + between literals and a few variables is fine. The quadratic trap is specifically a loop problem.

---

The Short Version

• Strings are immutable in Python, Java, JavaScript, Go, and most mainstream languages. The underlying bytes cannot change after allocation.
• Immutability enables four concrete wins: string pool deduplication (one copy per identical value), hash code caching (O(1) map lookups), zero-cost thread sharing, and a security guarantee against TOCTOU races.
• Concatenation in a loop is O(n²) because each iteration copies the entire current string. Total copies = k + 2k + 3k + ... + nk = k·n(n+1)/2.
• The fix: accumulate into a mutable buffer and finalize once. "".join() in Python, StringBuilder in Java and C#, strings.Builder in Go.
• At n = 100,000, the difference between O(n) and O(n²) is the difference between a millisecond and a second of pure copy work.

This kind of complexity reasoning, tracing through what actually happens in memory rather than pattern-matching to a known result, is exactly what interviewers want to hear out loud. If you want to practice narrating that analysis under time pressure, SpaceComplexity runs voice-based DSA mock interviews that score precisely this kind of thinking.

For more on the string patterns that show up in coding interviews, see String Internals and the Interview Patterns Behind Them.

---

Further Reading

• Why are Python Strings Immutable - GeeksforGeeks
• Why Java Strings are Immutable - GeeksforGeeks
• Guide to Java String Pool - Baeldung
• strings.Builder - Go Packages
• Using the StringBuilder Class in .NET - Microsoft Learn