Big-O: choosing list, dict, or set

The cost model in one table

Big-O notation was invented so engineers can predict, before running anything, whether code that works on a hundred records will survive ten million. It is also the shared language of technical interviews.

Big-O describes how an operation's cost grows with the size n of the data. O(1) stays flat no matter the size, and O(n) grows in step with it.

The headline is that membership tests on a list scan every element, while dicts and sets jump straight to the answer.

They can do that because of hashing. A hash function converts any key into a number, and that number decides which slot of the underlying table the entry lives in. To answer x in s, Python hashes x and inspects that one slot instead of walking the collection, so the cost stays flat as the data grows.

One list membership test inside one loop over the same data means O(n²), the classic accidental slowdown. Converting the lookup side to a set is often the entire fix.

Timing a list scan against a set lookup

Both collections hold the same 100,000 numbers and give the same answers, but the set version does dramatically less work per lookup. This code times both and reports which won.

import time

haystack_list = list(range(100_000))
haystack_set = set(haystack_list)
missing = -1

start = time.perf_counter()
for _ in range(200):
    missing in haystack_list
list_time = time.perf_counter() - start

start = time.perf_counter()
for _ in range(200):
    missing in haystack_set
set_time = time.perf_counter() - start

print("answers match:", (missing in haystack_list) == (missing in haystack_set))
print("set wins:", set_time < list_time)

Output

answers match: True
set wins: True

The value -1 is deliberately absent from both collections, which forces the list into its worst case. Nothing matches, so the scan cannot stop early and has to touch all 100,000 elements before concluding the item is missing. The set hashes -1 once and looks at a single slot.

time.perf_counter() is the right clock for measuring short durations, and the comparison is printed as a boolean rather than raw seconds because exact timings vary with the machine.

Reading your own code for cost

Estimate cost by multiplying loops:

for order in orders:            # n times
    if order.id in seen_list:   # O(n) scan each time -> O(n²) total
        ...

Swap seen_list for a set and the same loop is O(n). Common cost profiles you now recognize:

• Sorting is O(n log n). Sorting once then doing clever O(1) work often beats repeated scans.
• Counter(items) is a single O(n) pass.
• Slicing a list copies, so xs[1:] inside a loop hides another O(n).

Do not micro-optimize readable code that is already O(n). Do fix the accidental O(n²), because at a million records that is the difference between one second and days.

find_duplicates

A version of this function that keeps seen as a list is O(n²), because each in test rescans everything collected so far. Making seen a set drops the whole function to O(n) while producing byte-identical output.

def find_duplicates(items):
    seen = set()
    dups = []
    for item in items:
        if item in seen:
            dups.append(item)
        else:
            seen.add(item)
    return dups

print(find_duplicates(["a", "b", "a", "c", "b", "a"]))

Output

['a', 'b', 'a']

Two changes did it: seen = set() instead of an empty list, and seen.add(item) instead of append. The membership test now costs O(1), so n iterations total O(n) rather than O(n²).

Notice that dups stays a list on purpose. Its job is to report duplicates in the order they were discovered, and a set would both lose that order and collapse the third "a" into the first.

The worst case for a list membership test

Checking x in xs where xs is a 1,000,000-item list can cost up to 1,000,000 comparisons.

List membership is a linear scan from the front, so the worst case is the one where the item is absent. Nothing ever matches, the scan can never return early, and it touches every element before it can honestly answer False.

The same test on a set hashes x and inspects the single slot that hash points to, which is O(1) on average regardless of size. That gap is why "make it a set" fixes so many mysteriously slow programs.

Multiplying loop cost by body cost

A loop over n items that performs a set membership check on each pass costs O(n) in total: n iterations multiplied by O(1) of work per iteration.

The identical loop with a list membership check costs n × O(n) = O(n²), which is exactly the trap find_duplicates was rescued from above.

That multiplication is the whole technique for reading cost out of your own code. Find the loop, work out what one pass of the body costs, and multiply. Nested loops multiply again, which is why an innocent-looking in on a list inside a loop is worth spotting immediately.