Strings: Immutability, Builders, and the Hidden O(n)

Here is the most innocent-looking loop in programming:

function slurp(lines):
    result = ""
    for each line in lines:
        result = result + line
    return result

Read lines, glue them together. Everyone has written it. Now feed it a real file. Ten thousand lines: instant. A hundred thousand: a noticeable pause. A million lines, about a hundred megabytes of text: minutes, sometimes much longer. Count the steps the way lesson 1 taught you and the loop looks like O(n), one append per line. The stopwatch disagrees, and by the end of this lesson you'll be able to put a number on how wrong that count is. The number is measured in terabytes.

The structure responsible is the one lesson 3 ended by pointing at: the string. A string is an array of bytes wearing a trenchcoat. Everything from the last two lessons applies, contiguous block, cache lines, grow-and-copy, all of it. But the trenchcoat hides one rule that changes the entire cost model.

An array wearing a trenchcoat

Pull the coat open and the picture underneath is familiar. A string in Go, Java, Python, or JavaScript is a small header over a contiguous block of bytes:

struct string:
    data: pointer to a block of bytes
    len:  integer                      # stored, not computed

So the prices you already know carry over. Indexing a byte is O(1), base plus offset. Scanning is sequential, cache-friendly, prefetcher-streamed. And len(s) is O(1) because the length is a field: asking for it reads one integer that's already there.

That last one sounds too obvious to say out loud, except you've already seen what happens without it. C does not store a length. A C string is just bytes ending in a zero byte, so finding the length means walking the bytes until you hit the terminator. That's strlen, and that's what sscanf called in the GTA Online story from lesson 1: ten megabytes walked per token, 63,000 times. The two-word header with a stored length is that fix, institutionalized into every language designed since.

Now look at what's missing from the header compared to lesson 3's dynamic array: no capacity. No spare room, because there is no append. You cannot change a string.

Frozen on purpose

Not one character. In Python, Java, JavaScript, Go, and C#, every operation that looks like it edits a string actually builds a new one. s.toUpperCase(), strings.ReplaceAll, s.strip(): all of them allocate. Five language design teams independently locked the same door, which suggests the reason is structural, not stylistic.

Here's what would break. Take a Python dict and insert a value under the key "alice". The dict hashes the key, and the hash picks the bucket where the entry lives (the full machinery is lesson 12; the one fact needed here is that where the entry is stored depends on the key's bytes at insert time). Now suppose strings were mutable and some other code, holding a reference to that same key string, changed one character: "alice" becomes "alicf". The entry doesn't move. It is still sitting in the bucket that "alice" hashed to. Look up "alicf": hashes to a different bucket, nothing there. Look up "alice": right bucket, but the stored key no longer matches. The entry still exists, consumes memory, and no key on earth can reach it. The dict is silently corrupted, and nothing ever threw an error.

Freeze the string and that failure mode is gone, plus three bonuses fall out of the same decision:

• Hash caching. If the bytes can never change, the hash can be computed once and stored inside the string object. CPython does exactly this, which is part of why string-keyed dict lookups are so fast. Lesson 12 cashes this in.
• Safe sharing. Pass a string to a function, store it in two collections, hand it to another thread: nobody needs a defensive copy and nobody needs a lock, because nobody can mutate it under you.
• Interning. If "true" appears ten thousand times, the runtime can keep one copy and point everyone at it. Java interns string literals; CPython interns identifier-like strings. Only safe because they're frozen.

Immutability isn't a restriction; it's a bargain. The price is the rest of this lesson.

The hidden O(n)

What does s + t cost? Both inputs are frozen, so there is exactly one way to implement it: allocate a fresh block of size len(s) + len(t), copy all of s in, copy all of t in. Concatenation copies both of its inputs, in full, every time. One innocent +, and the cost is O(len(s) + len(t)).

Now replay the opening loop with that price tag. Append 1 copies one line. Append 2: result already holds one line, so copy it plus the new one. By append number k, result holds k − 1 lines and you copy all of them again just to add one more. Total work:

1 + 2 + 3 + ... + n  ≈  n²/2  line-copies

The same parabola from lesson 1, the same disease as GTA's duplicate scan, the same shape as lesson 3's fixed-step growth. Concrete numbers: a million lines of 100 bytes each. The finished string is 100MB. The copying along the way totals about 10⁶ × 10⁶ / 2 × 100 bytes ≈ 50 terabytes of bytes moved. Fifty terabytes of memcpy to build a hundred megabytes, which even at memory bandwidth of tens of gigabytes per second is the better part of an hour spent purely on copying.

The loop looks O(n) because you count appends. Each append secretly costs the current length. A hidden O(n), stacked n times, is O(n²).

Shlemiel the painter

This trap is old enough to have a name. In 2001, Joel Spolsky's essay Back to Basics told a joke about Shlemiel, who gets a job painting the lines down the middle of a road. Day one he paints 300 yards, day two 150, day three 30. Asked to explain the collapse, Shlemiel says: "I can't help it. Every day the paint can stays where I started, and every day I have to walk farther and farther back to dip the brush!"

Spolsky told it about C's strcat, which has it even worse than our loop: no stored length, remember, so before appending a single byte strcat must walk from the start of the destination just to find the end. Concatenating n pieces with strcat re-walks everything per piece, the GTA bug's close cousin.

But the loop above is Shlemiel even with a stored length: it re-copies the whole road every day. Engineers genuinely call these Shlemiel the painter algorithms, and once you know the name you see him everywhere work already done gets redone on every step. The fix is always the same idea: keep the paint can with you.

Builders are dynamic arrays of bytes

You built the paint can last lesson. A builder is a dynamic array of bytes: pointer, length, capacity, doubling on growth. That is the entire secret behind Go's strings.Builder, Java's StringBuilder, and Python's idiom of appending parts to a list and calling "".join(parts) at the end.

Run lesson 3's prices on it. Each append lands in spare capacity: write, bump, O(1). The occasional doubling copies what's there, and all doublings ever performed sum to under 2n. At the end, one final O(n) conversion freezes the accumulated bytes into a real immutable string. Total: O(n). The 100MB file costs a few hundred megabytes of movement instead of fifty terabytes, milliseconds instead of an hour.

join is sharper still: it makes one pass to sum the lengths of all the parts, allocates the exact final size once, then copies each part into place. No doubling, no wasted capacity. That is lesson 3's pre-sizing, applied automatically. If you drive a builder by hand and know the final size, say so: Grow(n) in Go, ensureCapacity(n) in Java, reserve(n) in C++.

The fine print: when += secretly works

Benchmark this yourself and two languages will appear to make a liar out of me. Both are worth understanding, neither changes the advice.

CPython cheats. Run the += loop in CPython and it's often fine, linear even. When the string on the left has a reference count of 1, no other code can observe it, so the interpreter quietly resizes it in place, mutating the immutable where nobody can catch it. It's a beautiful trick and a terrible contract: hold a second reference to the string and it evaporates; run on a different Python implementation and it evaporates. The official Python docs still tell you to use join, because the trick is an implementation detail, not a promise.

V8 builds ropes. Modern JavaScript engines often don't copy on + at all. V8 returns a cons string: a tiny two-pointer node that says "left half, right half", deferring the copy and flattening the tree only when something needs the actual bytes. So += in a loop in modern JS is usually fine too (the rope data structure generalizes this idea; we won't need it again in this course).

So why teach the quadratic at all? Because these are engine internals, not contracts; they vary by runtime, version, and the exact shape of your code. The model is: concatenation copies. When an engine saves you, it's a gift. Take the gift, don't build on it. Write the builder and you are fast in every language, every runtime, every version.

The other tolls

Concatenation is the famous hidden O(n). It is not the only one.

Slicing copies. s[1:] in Python allocates and copies n − 1 bytes. Take slices inside a loop and you're Shlemiel again. Most languages copy on slice, and after the next paragraph you'll see why that's the safe default.

Except in Go, where slicing shares. A Go substring is a new header over the same bytes: O(1), no copy, lesson 3's aliasing story wearing the trenchcoat. Fast, and sharp: pull a 10-byte token out of a 100MB document and keep the token, and it pins the entire 100MB, because the garbage collector cannot free a block while anything points into it. The standard antidote is an explicit copy when you intend to keep a small piece of a big string (strings.Clone exists for exactly this). Java's history here is delicious: Java substrings shared their backing array for seventeen years, until Java 7 update 6 in 2012, when the JDK switched substring to copying, precisely because of the pinning bug. Two languages, same trade, opposite answers, and you can now argue both sides.

Comparison and search are O(n). Equality walks both strings until a mismatch (length check first, which is O(1) and settles most non-equal pairs). Finding a substring is at least O(n). The clever pattern-matching algorithms that improve the constant live in a later course; the floor is linear, because you can't know what you haven't read. Only the length is free.

Bytes are not characters

One last pocket in the trenchcoat. This whole lesson priced strings in bytes, and bytes are not characters. In UTF-8, the encoding of essentially the modern internet, a is one byte, é is two, 💩 is four, and a family emoji is several code points glued together with zero-width joiners. Three consequences:

• "Length" is ambiguous. len("💩") is 1 in Python (code points), 2 in JavaScript (UTF-16 code units), 4 in Go (bytes). None of them is wrong; they count different units, and none of them counts what a user would call "one character" (the user-perceived unit is a grapheme cluster).
• Indexing by character is O(n). With variable-width encoding, code point number i has no fixed byte offset, so reaching it means walking from the start. Go's range over a string does this decoding for you; utf8.RuneCountInString is an honest O(n).
• The bug class is real. Truncate a username to "100 characters" by slicing bytes or UTF-16 units and you can cut an emoji in half, shipping a broken half-character that renders as garbage or crashes a strict serializer downstream.

The rule: for cost, think in bytes. For text, cut only at boundaries a real Unicode library gives you, never with raw len and a slice. That's the one honest beat this lesson owes you; Unicode in full is its own course.

The race, in real code

The videos stay in pseudocode; here is quadratic-versus-builder in the three languages this course carries. C++ is the odd one out, because std::string is mutable. C++ declined the immutability bargain, so the builder is built in: += on a std::string appends in place using exactly lesson 3's capacity-doubling machinery. The trap in C++ is spelled differently, as you'll see in its tab.

function slurpQuadratic(lines: string[]): string {
  let result = ""
  for (const line of lines) result += line // the model: copies result each time
  return result // (V8's ropes often rescue this; don't build on it)
}
 
function slurpLinear(lines: string[]): string {
  return lines.join("") // one length pass, one exact allocation, one copy pass
}

func slurpQuadratic(lines []string) string {
	result := ""
	for _, line := range lines {
		result += line // allocates a new string, copies both sides, every time
	}
	return result
}
 
func slurpLinear(lines []string) string {
	var b strings.Builder
	total := 0
	for _, line := range lines {
		total += len(line)
	}
	b.Grow(total) // pre-size: one allocation, lesson 3's antidote
	for _, line := range lines {
		b.WriteString(line) // write, bump: the O(1) fast path
	}
	return b.String()
}

std::string slurp_quadratic(const std::vector<std::string>& lines) {
    std::string result;
    for (const auto& line : lines)
        result = result + line; // builds a fresh temporary, copies everything
    return result;
}
 
std::string slurp_linear(const std::vector<std::string>& lines) {
    size_t total = 0;
    for (const auto& line : lines) total += line.size();
    std::string result;
    result.reserve(total);          // pre-size
    for (const auto& line : lines)
        result += line;             // appends in place: already a builder
    return result;
}

Walk the difference in the C++ pair: result = result + line evaluates result + line first, which allocates a temporary and copies both sides (the immutable cost model, reproduced by accident), then assigns it back. result += line appends into spare capacity. One character of syntax, the difference between O(n²) and O(n). Time any of the three pairs on a million short strings and the gap is not subtle.

Where this shows up in production

The quadratic concat is one of the most-flagged performance bugs in existence. IntelliJ ships a "string concatenation in loop" inspection for Java; javac itself rewrites single-expression concatenation (a + b + c) into efficient builder code, but it cannot rescue a += inside a loop, which constructs and discards intermediate strings every iteration. Anything that assembles text at scale, JSON encoders, template engines, loggers, SQL builders, writes into a growable byte buffer (strings.Builder and bytes.Buffer underneath Go's encoding/json, StringBuilder underneath Java's logging frameworks) rather than concatenating. And the Go substring-pinning gotcha is a recurring real-world memory leak: a service that reads large request bodies and stores small extracted tokens can hold gigabytes hostage, which is why strings.Clone was added to the standard library in Go 1.18.

That closes the first module. The cost of everything: you can read a growth curve (lesson 1), you know what a step physically costs (lesson 2), you've built the machine under every list (lesson 3), and you've seen the cost model strings hide under the coat. From here the course stops asking "what does it cost?" in the abstract and starts spending that vocabulary on structures and the patterns they unlock. First up is the structure these four lessons kept tolling: the linked list has spent the whole module as the cautionary tale, the anti-array, the pointer chase. Next lesson it gets its day in court: what linked lists actually buy, and the situations where they genuinely beat arrays.