Why does deduplicating invitee addresses with a membership check on a growing collection cost O(n^2)?
answer
- one line, but how much work inside?
- the checked collection grows every step
- cost of step k is proportional to k
- the sum 1+2+...+n is quadratic
- swap the scan for expected O(1) lookup
basics
~20 sEach membership check scans everything kept so far, so the check at step k costs O(k), not O(1). Summing 1 through n gives O(n^2). A hash-based set makes each check expected O(1), so the whole pass becomes O(n).
solid answer
~50 sThe loop body looks like three cheap lines, but one of them is a search. A membership check against a linear sequence walks it element by element, so at step `k` it inspects up to `k` addresses. The total is `1 + 2 + ... + n = n(n+1)/2`, which is O(n^2) even though there is only one visible loop. The fix is to change the structure, not the loop: keep the already-seen addresses in a hash-based set, where a lookup is expected O(1) (O(n) worst case if hashing degenerates), giving an O(n) pass overall. If you also need the output in first-seen order, keep the set purely for membership and append accepted addresses to a separate output sequence — order is preserved and the cost stays linear. The lesson generalises: when counting loop cost, every call in the body carries its own complexity.
code
pseudocode · 13 linesseen = empty sequence
unique = empty sequence
for i in 0..n-1:
addr = invites[i]
if not member(seen, addr): // scans seen left to right
append(seen, addr)
append(unique, addr)
return unique
// member(s, x):
// for j in 0..length(s)-1:
// if s[j] == x: return true
// return falsego deeper
Be ready to point at the membership call and say it hides a scan whose length grows each iteration, so the total is O(n^2). Then name the hash-based set as the fix and say the pass becomes O(n).
Explain the arithmetic explicitly: 1 + 2 + ... + n = n(n+1)/2. Then state the set bound precisely as expected O(1) with an O(n) worst case, and mention the O(n) extra space you traded for it.
Show how you would catch this in review before it ships: read every call in a loop body as the loop it contains, and ask whether the collection being searched grows with the input or is bounded by validation.
Own the framing that quadratic is a risk profile, not a verdict. Argue when the scanning version is the right code to keep, and what guardrail — an input cap, a load test at ten times today's size — makes that choice defensible later.
## The shape of the bug You are reviewing a diff. An event service collects invitee addresses from several sources and must drop duplicates before sending. The new code reads like this: ``` seen = empty sequence unique = empty sequence for i in 0..n-1: addr = invites[i] if not member(seen, addr): append(seen, addr) append(unique, addr) ``` There is one loop over `n` items, so the instinct is "O(n)". That instinct is the misconception this leaf exists to kill: **one line is not one operation**. `member(seen, addr)` is a call, and a call has its own cost. ## Counting what the call actually does A membership check against a *linear* sequence (a dynamic array, a linked list — anything without an index on the values) has no choice but to compare the target against elements one at a time until it finds a match or runs off the end. Its cost is proportional to the length of what it scans. Here the scanned collection grows: it holds 0 elements on the first iteration, 1 on the second, and up to `k` on iteration `k`. Worst case (all addresses distinct, so nothing short-circuits early) the total number of comparisons is: `0 + 1 + 2 + ... + (n-1) = n(n-1)/2` That is a triangular sum, which is `~n^2/2`, so the pass is **O(n^2)**. The visible loop contributes the `n`; the hidden scan inside it contributes the second `n`. The nesting is real, it is just spelled as a function call instead of a second `for`. A useful habit: when you analyse iterative code, mentally rewrite each library call as the loop it contains. `member` becomes `for j in 0..length(seen)-1: if seen[j] == addr: return true`. Once it is a loop on the page, nobody argues about the multiplication. ## The fix is a structure, not a cleverer loop People who spot the quadratic sometimes try to fix the *loop* — break early, scan backwards, skip every other element. None of that changes the class. What changes the class is giving the membership question a data structure that can answer it without scanning: a hash-based set. Hashing the address turns it into a bucket index directly, so a lookup touches a small, bounded number of entries. State the bound honestly, because interviewers listen for this: hash-set lookup is **expected** O(1), and O(n) worst case when many keys land in one bucket (a bad hash function, or an adversary choosing keys). Production hash sets defend against that with randomised or keyed hashing and with better-than-linear bucket structures, but the guarantee is expected/amortized, never "O(1), full stop". With expected O(1) lookups the pass is O(n) expected, plus O(n) extra space for the set — a classic space-for-time trade. There is a second legitimate fix if you may reorder: sort the addresses (O(n log n)) and drop neighbouring equals in one linear pass. It is asymptotically worse than the hash approach but uses no extra table and yields sorted output, so it is a real option, not a wrong answer. ## Cost of the element comparison itself One more layer that separates a careful answer from a memorised one: the `n` in `O(n^2)` counts *comparisons*, and comparing two addresses is not free either — it costs time proportional to their length `L`. So the honest bound is O(n^2 · L) for the scanning version and O(n · L) expected for the set version (hashing an address also reads all `L` characters). If the code normalises each address — lowercasing, trimming — do that **once per element** before the loop body's decision, not inside the scan, or you multiply an O(L) job by the scan length too. ## When it does not matter Quadratic is not automatically a defect. If invitees are capped at a couple hundred by validation, `200 · 200 / 2 = 20,000` comparisons is microseconds and the scanning version may well be the clearer code. What makes it a review comment is *unbounded* input: a list that grows with the customer, an import path fed by a file upload, a job that will be reused on a bigger source next quarter. Say which case you are in; that is the difference between complexity theatre and engineering judgement.
- Does moving to a hash-based set make the worst case O(n) as well?No. It makes the pass O(n) expected. If many addresses collide into one bucket — a weak hash function, or keys chosen adversarially — individual lookups degrade toward O(k) and the pass toward O(n^2). Production sets reduce that risk with randomised or keyed hashing and non-linear bucket handling, but the honest phrasing stays expected/amortized rather than guaranteed.
- The output must keep first-seen order. Does the set fix still work?Yes, and it is the standard shape. Use the set only to answer "have I seen this?", and append each newly accepted address to a separate output sequence in the order the loop encounters it. Membership is expected O(1), appending is amortized O(1), so the pass stays O(n) and first-seen order is preserved exactly.
- Addresses must match case-insensitively. Does normalisation change the complexity?Not if you normalise once per element, before the membership decision: that adds O(L) per address for length L, so the pass is O(n · L) expected. It does change things if you normalise inside the comparison, because then every one of the up-to-k comparisons per step re-does the O(L) work and you multiply a scan by a scan.
Checking a name against a paper guest list means reading down the page every time; the page gets longer with each guest you add. A card index keyed by name answers the same question in one reach, however many guests there are.
saying these in an interview costs you the question
- Calls it O(n) because there is only one visible loop
- Assumes a membership check is O(1) because it is one line
- Says hash lookups are O(1) with no expected-case caveat
- Tries to fix the loop instead of changing the structure
- Ignores that the scanned collection grows each iteration