Foundations — Generator expressions — memory efficiency

Before you can trust the parent note's claim that a generator uses $O(1)$ memory while a list uses $O(n)$, you must own every symbol and word it leans on. We build them from nothing, in the order they depend on each other. Nothing is used before it is defined.

1. What is an item? (the atom of everything)

Picture a single sandwich on a plate. That one sandwich is an item. When we later say "one item at a time", we mean exactly one plate in your hands.

Why the topic needs it: the whole memory argument is "how many items exist at the same moment". So "item" is the unit we will count.

2. What is a collection / sequence?

Picture a whole stack of plates on a table. Each plate is an item (section 1); the stack is the collection. The key question that this entire topic answers is:

Must all the plates sit on the table at once, or can we serve them one plate at a time?

A list is the "all plates on the table" answer. A generator is the "one plate at a time" answer.

3. The letter $n$ — "how many"

Why a letter instead of a number? Because we want a statement that is true for every size at once. Writing $n$ lets us say "no matter how big the stack gets…". Picture the stack of plates growing taller and taller — $n$ is its height.

We will meet $n$ again inside $O(n)$, so lock it in now: $n$ = count of items.

4. Memory — the desk, not the kitchen

Picture two desks side by side.

• Left desk (a list): all $n$ plates stacked on it simultaneously. Big stack → big desk needed.
• Right desk (a generator): exactly one plate at any instant, plus a tiny sticky-note that says "how to make the next plate".

Why the topic needs it: "memory efficiency" is literally how much desk space you need. The sticky-note is the crucial trick — read on.

See Memory management in Python for how Python actually allocates this desk space.

5. The recipe (state) — the sticky-note

For $(x\cdot x\text{ for }x\text{ in }\dots )$ the sticky-note holds just two things: "the last $x$ I used" and "the rule: square it, then step $x$ up by one". That note stays the same size whether the sequence is 5 items or 5 billion — it never lists the items, only how to get the next one.

This is the heart of Lazy evaluation: compute a value only when it is actually asked for, never in advance.

6. Iterate / on demand / yield one at a time

Picture pressing a "NEXT" button. Each press: the current plate leaves your hand, the recipe makes the following plate, and it lands in your hand. You are never holding two.

The mechanism behind the NEXT button is the iterator protocol — see Iterators and the iterator protocol. The def/yield sibling that produces values the same way is covered in Generator functions and yield.

7. Exhausted — the button stops working

Picture the printer after the final page: press NEXT and it just clicks, empty. This is why the parent warns you can't loop a generator twice. The plates you ate are gone; to eat again you must write a new recipe.

8. Big-O: $O(1)$ and $O(n)$ — measuring how the desk grows

Now the symbols $O(1)$ and $O(n)$. They describe how the desk space changes as $n$ grows, ignoring fixed clutter.

Picture two lines on a graph as $n$ increases:

Why "1" for a generator? Because "one plate + one sticky-note" is a fixed amount that does not depend on $n$. In Big-O we call any fixed amount $O(1)$ — literally "grows like the constant 1". Deeper treatment lives in Big-O space complexity.

9. The syntax symbols: () vs [] and the pieces inside

That single-character swap is the difference between the two desks in section 4.

Prerequisite map

Equipment checklist

You are ready for the parent note if you can answer each of these out loud:

Now proceed to the parent topic.