3 / 8 Typing & Performance

Set Membership Versus List Membership

Both functions answer the same question for a user id:

user_ids = list(range(50_000))
seen = set(user_ids)

def is_registered_slow(uid: int) -> bool:
    return uid in user_ids

def is_registered_fast(uid: int) -> bool:
    return uid in seen

As the number of registered users grows, why does is_registered_fast scale better, and what determines each function's cost?

A

Both are O(log n), because Python keeps both lists and sets sorted internally and locates elements with binary search.

B

is_registered_slow is O(n) on average: in on a list has no index to consult, so it scans elements one at a time until it finds a match or reaches the end. is_registered_fast is O(1) on average: a set is a hash table, so it computes hash(uid), jumps straight to the matching bucket, and compares against only the handful of keys that landed there.

C

Both run in O(n), because building seen = set(user_ids) already costs O(n), which cancels out any advantage the set gives on lookups.

D

is_registered_fast is O(1) even in the worst case, because two different keys can never land in the same hash bucket.