Generator expressions — memory efficiency: Visual walkthrough

Before line one, three plain words we will use everywhere:

We will build up to the parent's headline result: $M_{list} = O (n) versus M_{gen} = O (1)$ and understand what every symbol in it is doing.

Step 1 — What "storing an item" costs

WHAT. Let's give a name to the space one box takes. Call the space of item number $i$ the symbol $s_{i}$ (read: "ess-sub-eye"). The little $i$ is a label, like a jersey number — $s_{1}$ is the space of the 1st item, $s_{2}$ of the 2nd, and so on.

WHY this symbol. We need a way to talk about "how big is one item" without pretending all items are the same size. Some numbers are small, some big; $s_{i}$ lets each item have its own honest size.

PICTURE. One box, sitting on the desk, labelled with the space it eats.

Figure — Generator expressions — memory efficiency

Step 2 — A list stacks EVERY box at once

WHAT. A list comprehension like [x*x for x in range(n)] runs to completion immediately. It produces item 1, keeps it. Produces item 2, keeps it. … Produces item $n$ , keeps it. Nothing is thrown away.

WHY. A list's promise is "you can look at any item, any time, in any order" (e.g. L[0] or L[999]). To keep that promise it has no choice but to hold all boxes at once.

PICTURE. Watch the desk fill left-to-right; the red box is the one being made right now, but the black ones behind it never leave.

Step 3 — Add up the boxes: the list's memory is a sum

WHAT. Total memory of the list = a small fixed cost for the list's own "header" (its wrapper, length counter, etc.), plus the space of every single box it holds.

WHY a sum, and why now? A sum ( $\sum$ , the "add-all-of-these-up" sign) is exactly the tool for "one contribution per box, over all boxes." We reach for it precisely because Step 2 showed every box stays — so every box contributes.

PICTURE. The stack from Step 2, with a brace gathering all boxes into one grand total.

If every box is roughly the same size $s$ , the sum is just $n \times s$ . That $n$ is the key: double the items, double the memory. We write this growth as $O (n)$ — see Big-O space complexity: the " $O (n)$ " means "grows in proportion to $n$ ."

Step 4 — A generator refuses to stack. It makes, hands over, forgets.

WHAT. A generator expression (x*x for x in range(n)) does the opposite of eager. When you ask for the next value it: computes one box, hands it to you, and discards it before making the next. This is Lazy evaluation — compute only when asked, only what's asked.

WHY it can do this. A generator makes a weaker promise than a list: "you get each item once, in order, and then it's gone." Because it never promises random access, it never needs to keep old boxes. (This is exactly why re-iterating an exhausted generator gives nothing — the parent's steel-man.)

PICTURE. The red box is the only one on the desk. The dashed ghost box on the left is the previous item — already forgotten. There is no growing stack.

Step 5 — Add up the generator's boxes: the sum collapses

WHAT. Apply the same accounting as Step 3. Memory = fixed cost + (space per stored box) × (number of boxes stored at once). But Step 4 showed the number stored at once is always 1.

WHY this is the whole trick. In Step 3 the multiplier was $n$ . Here the multiplier is $1$ — it does not care about $n$ at all. The $n$ -dependence vanishes from the total.

PICTURE. Two desks side by side: the list's growing staircase versus the generator's single flat box that never grows.

Step 6 — The edge cases (where does the story break?)

Every honest derivation must survive its corner cases. Here are the four that matter.

Case A — Empty input, $n = 0$ . List: [] still costs the header $C$ (an empty list is a real, if tiny, object). Generator: still costs $C_{gen}$ . Both are $O (1)$ here — no boxes, no difference. The gap only opens up as $n$ grows.

Case B — You genuinely need all items at once (e.g. sort, reverse, len). Then the generator gives you no advantage — because to sort you must hold everything, so you'd call list(gen) and pay $O (n)$ anyway. The win exists only when you consume items one-pass, in order (sum, for, any, next).

Case C — Consuming it twice. After one full pass the generator is exhausted — the recipe has run off the end of range(n). A second pass yields nothing. The picture: the printer is out of pages. Fix: rebuild the generator, or store a list if you truly need repeats.

Case D — You accidentally materialise it. list(x for x in range(n)) or sorted(gen) or [*gen] all silently rebuild the full stack — you're back to $O (n)$ . The parentheses saved nothing if you immediately pour them into a list.

The one-picture summary

The whole derivation on one canvas: the list's memory is a rising staircase (each new item adds a box, so total $\propto n$ , i.e. $O (n)$ ), while the generator's memory is a flat red line hugging the bottom (one box at a time, so total constant, $O (1)$ ). The vertical gap between them is the memory you save — and it grows without bound as $n \to \infty$ .

Recall Feynman retelling — the whole walkthrough in plain words

One box costs some space (Step 1). A list makes every box and never throws any away, so the boxes pile into a staircase — you sum all their sizes and the total grows with how many there are, $O (n)$ (Steps 2–3). A generator is a lazy printer: it prints one page, hands it over, forgets it, then prints the next — so at any moment there's exactly one box on the desk plus a tiny recipe saying "what's next." When you do the same sum, the "how many at once" is just $1$ , so the $n$ falls out and you're left with a flat, constant cost, $O (1)$ (Steps 4–5). The catches: an empty list is no different, you can't win if you need everything at once, the generator dies after one pass, and pouring it into list() puts the whole staircase back (Step 6). The single missing $n$ is the entire magic.

Connections

Parent topic (Hinglish)
List comprehensions — the eager staircase of Steps 2–3
Lazy evaluation — the "make-then-forget" principle behind Step 4
Iterators and the iterator protocol — where the generator's tiny recipe lives
Generator functions and yield — the def/yield cousin using the same one-box idea
Big-O space complexity — the $O (n)$ vs $O (1)$ language of the summary figure
Memory management in Python — how the boxes are actually allocated on the heap

Visual walkthrough — Generator expressions — memory efficiency