Introduction

The complexity of repeated string append depends on the data structure, not just the loop count. In immutable-string contexts, each append may copy earlier characters, which can push total work toward quadratic behavior. In mutable-buffer contexts, append is usually amortized linear over the final output size.

Why Immutable Strings Can Become Quadratic

An immutable string cannot be modified in place. If a loop runs n times and each step creates a new string from previous content plus new text, copy cost grows with current length.

Imagine appending one character per iteration. The first append copies about 1 character, the second copies about 2, and so on. Total copied characters are close to 1 + 2 + ... + n, which grows on the order of n^2.

1# Potentially O(n^2) in many runtimes
2s = ""
3for _ in range(100_000):
4    s += "x"
5print(len(s))

Some runtimes apply optimizations for local concatenation, so real timings can be better than worst-case theory. Still, complexity analysis should assume no special optimization unless language documentation guarantees it.

Why Builders and Buffers Are Usually Linear

Mutable builders keep an internal array and expand capacity occasionally. Most appends write at current end without copying the full accumulated string. Resizing events copy data, but if growth factor is geometric, average append cost stays constant, and total cost for n appends is linear in output size.

1// Amortized O(n) for n appended characters
2StringBuilder sb = new StringBuilder();
3for (int i = 0; i < 100_000; i++) {
4    sb.append('x');
5}
6String result = sb.toString();
7System.out.println(result.length());

The final toString usually performs one copy into an immutable String, which is expected and still keeps total work near linear.

Language-Specific Practical Patterns

Different languages have different idioms, but the principle stays the same.

Python

Use list accumulation and "".join(...) for many fragments.

1parts = []
2for i in range(100_000):
3    parts.append(str(i))
4out = "".join(parts)
5print(out[:20], len(out))

JavaScript

For many small chunks, array plus join is often more predictable than repeated concatenation in hot loops.

1const parts = [];
2for (let i = 0; i < 100000; i++) {
3  parts.push(String(i));
4}
5const out = parts.join("");
6console.log(out.length);

Java

Prefer StringBuilder in loops. If multithreaded shared access is required, use StringBuffer or external synchronization.

Complexity Framing That Avoids Confusion

People often ask whether this is O(n) or O(n^2), but there are two different n definitions.

• If n means number of append operations and each append adds fixed-size text, immutable naive append can trend quadratic.
• If n means final output length and you use a dynamic builder, total work is typically linear in that final length.

The disagreement usually comes from mixing these two interpretations.

Quick Benchmark Template

The simplest way to validate behavior on your runtime is to benchmark both approaches.

1import time
2
3def plus_equals(count: int) -> float:
4    s = ""
5    t0 = time.perf_counter()
6    for _ in range(count):
7        s += "x"
8    return time.perf_counter() - t0
9
10def list_join(count: int) -> float:
11    parts = []
12    t0 = time.perf_counter()
13    for _ in range(count):
14        parts.append("x")
15    _ = "".join(parts)
16    return time.perf_counter() - t0
17
18for count in (10_000, 20_000, 40_000):
19    print(count, plus_equals(count), list_join(count))

Benchmark on representative input sizes, not toy values, and run multiple rounds to reduce noise.

Common Pitfalls

• Declaring complexity without defining what n means.
• Assuming all runtimes optimize repeated concatenation identically.
• Benchmarking tiny strings and extrapolating to production scale.
• Ignoring memory pressure. Frequent intermediate string creation increases allocation and garbage collection overhead.
• Choosing thread-safe buffers by default when no sharing exists, adding unnecessary synchronization cost.

Summary

• Naive iterative append on immutable strings can approach quadratic total copy work.
• Mutable builders or chunk lists plus join usually provide amortized linear behavior.
• Complexity debates often come from inconsistent definitions of n.
• Runtime optimizations may help, but builder-style patterns remain the safest default.
• Benchmark with realistic input sizes before locking in an implementation.