Quiz
Warm-up from lesson 2-1: `word[4]` reads the 5th character of a string in O(1). What must be true about how the characters are stored for that to work?
A string is a frozen array
Under the hood a Python string is an array of characters, so indexing and slicing behave exactly like list indexing. But strings add one big rule: they are immutable. Once created, a string can never change. Every operation that looks like it edits a string actually builds a brand-new string and leaves the original untouched.
Why freeze them? Immutable strings can be safely shared everywhere without copies, cached, and (important for unit 6) used as dict keys, because their contents can never shift under you.
See both facts in action:
Code exercise · python
Run this. `upper()` returns a new string and leaves `s` alone, and trying to assign into a string is a TypeError.
The accidental O(n²) loop
Immutability has a performance trap. This innocent loop is quadratic:
result = "" for piece in pieces: result = result + piece # builds a NEW string every pass
Each + must copy everything built so far plus the new piece, because the old string cannot be extended. Copy 1 char, then 2, then 3... the triangle sum from lesson 1-2 again: O(n²) total.
The fix: collect pieces in a list (append is amortized O(1), lesson 2-2), then merge once at the end with "".join(parts), which copies each character exactly once. O(n) total.
Code exercise · python
Run this copy-counting comparison. `+=` concatenation copies the triangle sum of characters. `join` copies each character once. Same shape as doubling vs grow-by-one in lesson 2-2.
Code exercise · python
Your turn: build one CSV line the fast way. Append the strings "row1" through "row5" to a list (use an f-string in a loop), join them with a comma, and print the line, then print how many parts you collected.
Quiz
Why is building a big string with `result += piece` in a loop O(n²)?