Español

String += In A Loop Is O(n²), Use Join

This one-character habit makes your loop quadratic. += on a string inside a loop looks harmless — one operator, one line — but in Python it can turn an n-item build into O(n²) work. The fix is also one line.

Why += in a loop goes quadratic

Python strings are immutable: no operation changes a string in place. So s += part doesn't append — it allocates a brand-new string and copies all of s plus part into it, every single iteration.

Do that n times and the copying grows: 1 character, then 2, then 3 … roughly n²/2 character copies in total. Python's own FAQ states it plainly: concatenating many strings this way has a total runtime cost that is "quadratic in the total string length."

At 100 parts you won't notice. At 100,000 lines of a log file or a generated report, the loop that should take milliseconds takes minutes — and it gets worse the bigger the input, which is exactly when you can least afford it.

The fix: collect parts, join once

The recommended idiom, straight from the Python FAQ: accumulate the pieces in a list, then call str.join() once at the end.

# O(n²): copies the whole string every pass
result = ""
for row in rows:
    result += render(row)

# O(n): one allocation, one copy at the end
parts = []
for row in rows:
    parts.append(render(row))
result = "".join(parts)

list.append is amortized O(1), and "".join(parts) measures the total length, allocates once, and copies each part exactly once. Same output, linear time. If the loop body is simple, collapse it further: result = "".join(render(row) for row in rows).

Streaming builds: io.StringIO

When you're building text incrementally across functions — a code generator, an LLM-token accumulator, anything writer-shaped — a list of parts can feel awkward. io.StringIO gives you an in-memory text buffer with a file-like API, and the Python FAQ lists it as the other reasonably efficient idiom:

import io

buf = io.StringIO()
for chunk in stream:
    buf.write(chunk)
result = buf.getvalue()

Bonus: anything that expects a file object (csv.writer, print(file=...), template writers) can write straight into the buffer.

Rules of thumb

Power-user notes

• CPython sometimes hides the bug. CPython has a refcount-based optimization that can make s += part fast in some runs. PEP 8 tells you not to lean on it: the optimization "is fragile even in CPython (it only works for some types) and isn't present at all in implementations that don't use refcounting." Your code will be fine on your laptop and quadratic on PyPy — write the join() form.
• Bytes flip the rule. For bytes, the FAQ's recommended idiom is the opposite shape: extend a bytearray with +=. bytearray is mutable, so in-place append really is cheap.
• This is a classic AI-codegen smell. Assistants trained on tutorial-style snippets happily emit result += ... loops. When you review generated code, grep for += on a string inside for/while — it's a 10-second review win.
• Prove it with timeit. python -m timeit on 10k parts makes the gap visible in one command; measuring beats arguing.

Resources

• Python FAQ — What is the most efficient way to concatenate many strings together?
• str.join() — Python standard types reference
• io.StringIO — Python io module reference
• PEP 8 — Programming Recommendations (don't rely on CPython's += optimization)
• Python glossary — immutable