vizlearn

Why is `in` slow on a list but fast on a set?

Interview QuestionsBy Updated

x in list compares against each element until it finds one, so it is O(n) — and a miss always costs the full length. x in set computes where the value would be and looks there: O(1). Swapping one for the other is usually a one-character change with a thousandfold effect.

Overview

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.

Lists & arraysConceptualEasy

Step through it

What to watch

  • The list compares one element at a time and stops at the hit.
  • A miss checks all of them — the worst case is the common case.
  • The set makes one probe regardless of size.

Say this out loud

"`in` on a list is a linear scan, O(n). On a set or dict it's a hash lookup, O(1). If I'm testing membership repeatedly I build a set first - that's O(n) once instead of O(n) every time."

Why is `in` slow on a list but fast on a set?

What is the complexity of `x in my_list`, and how do you make it faster?

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.

Run it in Python

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.

membership.pyPython 3
Output
How the code works
  1. p in as_listA comparison per element until it matches. The probe for -1 is the worst case and the one that shows the real cost, because nothing stops it early.
  2. p in as_setHash, jump to the slot, compare. The timings barely move when n goes up tenfold, which is what O(1) looks like from outside.
  3. lookup = set(haystack)Built once, outside the loop. That converts O(n·m) into O(n + m) and is usually the entire fix.
  4. dict.fromkeys(items)Deduplicates while preserving order, because dicts have kept insertion order since 3.7. A set would lose it.
Change one thing
  • Move set(haystack) inside the comprehension. Rebuilding it per element is worse than the list version — the point is building it once.
  • Try x in some_tuple. Tuples are also linear; immutability does not buy a faster search.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. x in my_list has complexity:
  2. Testing membership repeatedly against a large list is best fixed by:
  3. Which deduplicates a list while preserving order?





 Cheat sheet
Why is `in` slow on a list but fast on a set?
x in list compares against each element until it finds one, so it is O(n) — and a miss always costs the full length. x in set computes where the value would be and looks there: O(1). Swapping one for the other is usually a one-character change with a thousandfold effect.
INTERVIEW · vizlearn.in/interview/why-is-in-slow-on-a-list.html
More in Interview
InterviewTwo SumInterviewMaximum subarray sum (Kadane)InterviewRemove duplicates from a sorted array in placeInterviewRotate an array by k
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact