Complexity, Annotated Not Asserted
addItem on an array is O(n) because it scans; on a map O(1) average because it hashes. Write that beside the operation where it is true, link the structure that explains it, and say the honest thing: for ten items the difference is invisible.
The situation, the reflex, and why it stalls
Every lesson starts where being stuck starts: someone has a problem, and the first move that comes to mind feels like progress.
Someone says "this should be O(1)". Where does that claim belong, how do you check it, and when is it true and still irrelevant?
I know the words. I can say that arrays are O(n) for search and hash maps are O(1). What I cannot do is look at my addItem and say what it costs, or answer a reviewer who writes "O(n)!" on the find line — I do not know whether that is a bug, a fact, or a fact that does not matter.
Treat complexity as a property of the structure and quote it from memory. "Arrays are slow to search" becomes a rule, so anything that scans an array is rewritten to hash, and the rewrite is justified by the quote rather than by the operation it changed.
Complexity quoted from memory is attached to the wrong thing. "Arrays are O(n)" is said of the cart; the cart's view is O(n) in any structure and its add is O(n) only because of the find, and the sentence hides which line the claim is about.
- Complexity quoted from memory is attached to the wrong thing. "Arrays are O(n)" is said of the cart; the cart's view is O(n) in any structure and its add is O(n) only because of the find, and the sentence hides which line the claim is about.
- The claim is never checked against size. O(n) with n bounded by a shopper's patience is a handful of comparisons, and the rewrite to O(1) trades that for a hash and a conversion at every boundary. Nothing was measured, so nothing was improved; something was asserted.
- The reviewer's "O(n)!" cannot be answered because there is no annotation to point at. If the line said "O(n) scan; cart is bounded by a shopper; flips to a map at thousands of entries", the review would be a conversation about the bound, not a mood about the notation.
- The learner concludes that complexity is an exam topic. It is a habit of writing a cost beside an operation and asking whether the cost is real at the size you have; taught as a table of structures, it never becomes the habit.
The move
Precisely enough to apply it to a problem you have never seen — not a slogan.
- Attach the cost to the operation, on the structure, at the line where it arises. Not "arrays are O(n)" but "addItem's find is O(n) on the array because it walks the items comparing product ids; on the map it is O(1) average because the key is hashed". The line is what the cost is about; the structure is why.
- Say what n is and what bounds it. Complexity is a statement about growth, and growth has to have something to grow with. For a cart n is distinct products in one cart, bounded by a shopper; for a server's cart store n is carts, bounded by shoppers; the same O(n) is a rounding error in one and a cost in the other.
- Say when the difference becomes visible, and mean it as a measurement to be taken rather than a number to be quoted. "Invisible below roughly a thousand entries; measure before switching" is an honest annotation. "O(1) is faster" is not, because at ten entries it is often false.
- Cross-link the structure that explains the cost rather than explaining it in the cart. The hash map lesson says why lookup is O(1) average and when it degrades; the annotation's job is to say that this line depends on it, so a reader who does not know can go one primitive lower and find out.
The costs, beside the operations they belong to
The matrix puts every cart operation against both in-memory representations and the database rows the concept reaches later. Read down a column and the structure's character appears; read across a row and the honest part appears — view and total cost the same everywhere, because they visit everything, and no structure makes visiting everything cheaper than everything.
The last row is the one that matters most and is easiest to leave out: what n is, and what bounds it. Without it the rest of the matrix is notation.
| Operation | Array of CartItem | Map<ProductId, CartItem> | Rows with unique (cart_id, product_id) |
|---|---|---|---|
| add (find existing) | O(n) scan — find walks the items comparing ids | O(1) average — the id is hashed | one indexed lookup + one write, per round trip |
| remove | O(n) filter — every entry visited | O(1) average | one indexed delete |
| change quantity | O(n) scan, then in place | O(1) average, then in place | one indexed update |
| view, in order | O(n), insertion order for free | O(n), order only where the language keeps it | O(n) rows, order by an explicit column |
| total | O(n) — a sum over everything | O(n) — the same sum | one query with SUM, still over every row |
| n is / bounded by | distinct products in one cart / a shopper | the same | the same per cart; carts per store for the index |
What the annotation looks like in the code
Here is the concept's own addItem with the annotation where it belongs: on the line that scans, naming n and its bound, with the honest note and the link. Nothing else in the function has a cost worth writing, and annotating it would hide the one line that does.
The note is what the reviewer's "O(n)!" would have been answered by. It is not a defence of the array; it is the record of why the array was acceptable and what would make it not.
1export function addItem(cart: Cart, productId: ProductId, quantity = 1): Cart {2 if (!catalog.has(productId)) throw new Error('unknown product')3 if (quantity <= 0) throw new Error('quantity must be positive')4 // O(n) scan: n = distinct products in this cart, bounded by one shopper.5 // Invisible at cart size; measure before switching. A Map<ProductId, CartItem>6 // makes this O(1) average (see DSA: hash-map) at the cost of a conversion7 // at every JSON boundary and an order guarantee that belongs to the language.8 const existing = cart.items.find((i) => i.productId === productId) // one entry per product9 if (existing) existing.quantity += quantity10 else cart.items.push({ productId, quantity })11 return cart12}The comment names the line, the n, the bound, the alternative and its cost, and says "measure". It does not say "arrays are slow" and it does not say "fast enough"; it says what would have to be true for either to be the case.
When "it should be O(1)" is right
The Why Ladder below takes the claim seriously rather than dismissing it. The rungs find what was actually needed — usually a bound — and the simpler thing that meets it; the last field says when the claim was right all along, because the device is not "constant time is a fad".
The ladder ends in a place the notation could not reach on its own: the question of what bounds n. That is the question a complexity claim is really about, and the one it usually skips.
“The cart's addItem should be O(1); the array scan is wrong.”
- ↓Why should it be O(1)? Because a scan grows with the number of items and lookups should not.
- ↓Why does growth matter here? Because if carts get large the add gets slow.
- ↓Why would carts get large? They would not — a cart is bounded by one shopper; the store's catalog is large, but the cart is a handful of lines from it.
- ↓Then what is the worry really about? A different n: the server holding every shopper's cart, where a scan by owner would grow with shoppers.
the claim was right when The cart is not bounded by a person — a wishlist with thousands of entries, a bulk order form, a cart merged from many devices — or key uniqueness must be structural because clients cannot be trusted to call find before push. Then the map, or the unique constraint, was right, and the annotation's switch condition was the sentence that said so.
The implementation ladder
Concept, examples, pseudocode, code, tests, production — for the concept this lesson is about. Code is the fourth tab, not the first.
Shopping Cart = A temporary collection of products the user intends to purchase, held between browsing and checkout.
- Does a cart have identity? Yes, weakly. Two carts with the same items are still two carts, because each belongs to someone and will become a different order. It needs an id once it leaves memory; in memory the variable is the identity.
- Who owns it? A shopper — a logged-in user or an anonymous session. The owner is part of the state because "my cart" has to be findable again.
- How long does it exist? From the first add until checkout or abandonment. Whether it survives a reload, a closed browser or a login is not a property of the concept; it is a persistence decision made later, and each answer changes where the cart lives.
- Should it survive reload? Usually yes for a store, usually no for a demo. V1 in memory says no; V2 browser storage says yes on one device; V3 server storage says yes everywhere the user is logged in.
- Should it survive login? Only if an anonymous cart and a logged-in cart are merged — a rule that does not exist in V1 and appears as a modification later.
- itemscollection of CartItemkeepThe cart is its items; without them nothing else means anything.
- items[].productIdidkeepThe reference to what is being bought. The catalog owns the product; the cart only points at it.
- items[].quantityinteger > 0keepTwo laptops is one entry with quantity 2, not two entries — the rule "one entry per product" needs a quantity to hold.
- owneruser id or session iddependsSo the cart can be found again by the person it belongs to.
- items[].productNamestringderiveIt would be convenient to render the cart without a catalog lookup.
- items[].pricemoneydependsThe total needs a price per item.
- totalmoneydropEvery screen shows the total.
- currencycodedependsPrices need a currency to be added.
- createdAttimestampdropAbandoned carts might be expired or emailed about.
- update Add item — the updated cart
- delete Remove item — the updated cart
- update Change quantity — the updated cart
- read View items — the list of entries — product id and quantity — for rendering
- domain Calculate total — the sum of price × quantity over the entries
- delete Clear cart — the empty cart
- • Every quantity is greater than zero.
- • One logical entry per product.
- • The total is never negative.
- • An unknown product cannot be added.
- • Quantity cannot exceed available stock — if inventory is enforced here.
How to do it
Most important first.
- For each operation on the chosen representation, write one annotation in the form "cost, because, n is, bounded by". Add: O(n) scan, because find walks the items, n is distinct products in the cart, bounded by a shopper.
- Where two representations are on the table, write the annotation for each and let the difference in the "because" be the comparison; the notation alone says nothing about which to choose (Array Cart vs Map Cart).
- Write the honest note where the cost is real only in theory. "For a cart this is invisible" is part of the annotation, not a concession; leaving it out turns an annotation into an assertion.
- When a claim like "should be O(1)" arrives, ask three things: which line, what is n, what bounds it. If the answers make the O(n) a rounding error, the claim is true and irrelevant, and saying so is the response.
- Link the DSA lesson for the structure at the annotation, not in a footnote. A reader who meets
Mapfor the first time needs the door beside the line that walked through it (Go One Primitive Lower).
Worked on a concrete problem
The move has to produce something. This is what it produced.
- The array cart's operations, annotated. add: O(n) scan — find walks the items comparing product ids; n is distinct products; bounded by a shopper; invisible at cart size. remove: O(n) filter — every entry is visited once. view: O(n), order preserved — every entry rendered. total: O(n) — one multiply and add per entry; unavoidable in any structure, because the total is a sum over all of them.
- The map cart's operations, annotated. add: O(1) average — the product id is hashed and the entry found without a walk; degrades toward O(n) only under pathological hashing, which the DSA lesson covers. remove: O(1) average. view: O(n), insertion order only where the language guarantees it. total: O(n) — the same sum, because no structure makes a sum over everything cheaper than everything.
- The reviewer's comment, answered. "O(n)!" on the find line. Response: "Yes — n is distinct products in one cart, bounded by a shopper; below roughly a thousand entries a scan and a hash lookup are indistinguishable without a measurement, and the array renders in order and serialises for free. The switch condition is written on the representation: a map when carts are large or held server-side keyed by owner." The comment was a fact; the annotation made it a conversation about the bound.
How you know it worked
What now exists that did not before, and what question you can now ask.
- Every operation on the chosen structure has a cost beside it that names the line, the n and the bound — and the note saying whether the cost is real at the size you have.
- The word "slow" has left the discussion; what remains is "O(n) where n is bounded by X", which two people can check.
- A complexity claim arriving from outside is answered by pointing at an annotation rather than by rewriting.
- The structure that explains the cost is one link away from the line that depends on it.
The questions you can now ask
The field this whole domain exists for. After this lesson, these are the questions to put to an unfamiliar problem.
- ?Which line does this cost arise on, and on which structure?
- ?What is n here, and what bounds it?
- ?At what size would this cost become visible — and is that a measurement I could take?
- ?Is this claim true and relevant, true and irrelevant, or a rule quoted from memory?
- ?Which lesson explains why this structure has this cost, and is it linked from the line?
What can go wrong
- Every line is annotated, including the ones whose cost is constant and obvious, and the annotations bury the two that matter. Annotate where the cost depends on the representation or on n; a
return cartneeds no cost. - The annotation is written and the measurement is never taken. "Invisible at cart size" is a prediction; when carts do grow, the annotation is the reminder to measure, and a reminder ignored is a stale claim in a comment (Measure Before You Optimize).
- The honest note becomes an excuse. "For ten items it does not matter" is true of the cart and false of a server scanning a hundred thousand carts by owner; the note is about a bound, and the bound has to be named, not assumed.
- The annotation replaces the DSA lesson instead of linking it. A comment that explains hashing in the cart file is a second, worse copy of the lesson; the link is the deliverable.
- Annotating costs takes attention away from behaviour, and on a first implementation behaviour is what is uncertain; the annotation pass is a second read, and for a counter it is a read with nothing to find.
- An honest "invisible at this size" invites the reply "then why annotate?" — the answer is that the size changes and the annotation is the record of what assumption the code rests on, which is a long-term benefit paid for now.
- Cross-linking instead of explaining means a reader without the DSA background has to leave the file to understand a line; explaining inline would keep them in the file and would also be wrong more often as the explanation drifts.
- "O(1) is always better than O(n)." It is better as n grows; at small n the constant factors decide, and a hash, a conversion and an allocation can lose to a short scan. Better is measured, not spelled.
- "Complexity is about the structure." It is about an operation on a structure for a given n. The array's view and total are O(n) exactly like the map's; only the find differs, and an annotation on "the array" would hide that.
- "The annotation is documentation, so it can be added at the end." It is a design record: the bound it names is the assumption the representation was chosen on. Written at the end it records a guess about why; written at the choice it records the reason.
Where this applies
Problem-solving advice is stated as universal far more often than it is. These labels say what each method is specific to — and where CONTESTED appears, the note gives the strongest form of the opposing view.
- GENERALWriting the cost beside the operation, with n and its bound, applies to any code that touches a collection; what differs by domain is whether the bound is a person, a catalog or nothing, and only the last makes the cost real by default.
- SCALE-SPECIFICFor a cart bounded by a shopper the honest note is "invisible"; for a server-side store of carts, the same O(n) scan by owner is the bottleneck on the first busy day. The annotation is the same; whether it is a warning or a shrug is decided by the bound.
- ILLUSTRATIVETen items, a thousand entries and a hundred thousand carts are stand-ins for the shape of the argument. The size at which a scan becomes measurable depends on the runtime and the item; the annotation says "measure", not "at a thousand".
Where the depth lives
This domain asks the question and hands the answer off by name.