Run it
The same membership tests against a list and a set at two sizes, then the loop that turns the difference from a curiosity into a quadratic.
Why it matters: the accidental quadratic
The cost only becomes visible when the membership test is inside a loop:
With 10,000 items on each side that is 100 million comparisons against 20,000 operations. The first version takes seconds; the second is instant.
This is the single most common performance bug in Python code, and it is dangerous precisely because both versions look correct and both are fast on small input. It passes review, it passes tests on a fixture of twenty records, and it becomes a production incident when the data grows.
The habit worth building: when you see a membership test, ask what container it is testing against, and whether it is inside a loop.
What a set costs
Converting to a set is not free, and the trade is almost always worth it:
Time: O(n) to build, then O(1) per lookup. Break-even is roughly one lookup — if you test membership more than once, the set wins.
Memory: a set uses more than a list of the same values, because it stores hashes and keeps spare capacity to bound collisions. Typically two to three times a list's overhead.
Requirements: the elements must be hashable. Lists and dictionaries cannot go in a set; tuples and frozensets can.
Order: a set does not preserve it. If order matters, dict.fromkeys() deduplicates while keeping insertion order.
That pattern — a set that grows as you scan — is the standard way to deduplicate a stream, and it stays constant-time per element throughout.
The two mechanisms
A list has no idea where anything is, so in walks it comparing element by element. Best case one comparison, worst case n, and a value that is absent always costs n.
A set stores values in slots chosen from their hashes. in hashes the value, goes to that slot and compares. The length of the set does not enter into it — see hash tables for the machinery.
The shape that turns quadratic
The damage is rarely a single lookup. It is a lookup inside a loop:
for x in candidates: if x in seen_list: ...
That is O(n·m). Building a set from seen_list once, before the loop, makes it O(n + m). This is the most common accidental quadratic in Python after pop(0), and it is invisible in testing because small inputs are fast either way.
When a list is still right
Building the set costs O(n) and some memory, so for a single membership test on a small list it is not worth it. The rule of thumb: if you will test more than a couple of times, or the collection is large, convert.
Sets also require hashable elements and lose ordering and duplicates. If you need order, a dict works as an ordered set since 3.7 — and dict.fromkeys(seq) deduplicates while preserving order in one line.
When a list is the right container anyway
The answer is not always "use a set". Lists are correct when:
Order matters and you need indexing.
Duplicates matter — a set collapses them.
The collection is tiny. For fewer than about ten elements, a linear scan is faster than hashing, because the constant factor of computing a hash exceeds a few comparisons.
Elements are unhashable — lists of lists, or of dictionaries.
You need every match, not just whether one exists.
The practical guidance: keep the list as the primary data, and build a set alongside it for membership testing. They are not mutually exclusive.
If the collection changes, the set must be kept in sync — which is a real maintenance cost and the main argument against doing it prematurely.
The same "looks fine, is linear" pattern appears in several other list operations:
| Operation | Complexity | Better |
|---|
x in lst | O(n) | set |
lst.index(x) | O(n) | A dict from value to index |
lst.remove(x) | O(n) | set.discard, or mark and filter |
lst.count(x) | O(n) | Counter |
lst.pop(0) | O(n) | deque.popleft() |
lst.insert(0, x) | O(n) | deque.appendleft() |
min(lst) in a loop | O(n) each time | A heap, or compute once |
sorted(lst) in a loop | O(n log n) each time | Sort once outside |
Every row is a linear operation that reads as constant-time. Recognising the shape — a linear operation inside a loop — is worth more than memorising the table.
How to demonstrate it
If asked to prove the difference, timing is more convincing than asserting:
Roughly four orders of magnitude, and the gap grows with the collection.
The other convincing demonstration is scaling: double the input and time it again. The list version takes twice as long per lookup; the set version does not change. That is what distinguishes O(n) from O(1) empirically, and it is the right way to answer "how do you know?"
Questions people ask
Why does in not use an index on a list? A list is an ordered sequence of arbitrary objects with no value-based structure. Maintaining an index would change what a list is, and cost memory and insertion time.
Is in on a string slow? It is a substring search, implemented in C with a tuned algorithm. Fast in practice, and still O(n×m) in the worst case.
Are sets always faster? No — below about ten elements a list scan wins, and building the set costs O(n).
What about frozenset? Same lookup performance, immutable, and therefore hashable and usable as a dictionary key.
Does a set preserve order? No. Use dict.fromkeys() to deduplicate while keeping order.
Why is the set worst case O(n)? If every element hashes to the same slot. That requires a pathological hash function or adversarially chosen keys, which is why Python randomises string hashes per process.
Recap in one screen
- A list has no value-based structure, so
in must scan — O(n). - A set hashes the value and looks in one place — O(1) on average.
- The bug is a membership test inside a loop: O(n×m) that looks correct and is fast on small input.
- Building a set is O(n) and pays for itself after roughly one lookup.
- The same shape applies to
index, remove, count and pop(0) — linear operations that read as constant.