Repeated x in data checks inside a loop are slow. data is a list of 1M items. Fix?

Options

1. Sort the list once so the checks run faster
2. Build a set once, so each check is O(1) (Correct option)
3. Convert it to a tuple, which searches faster
4. Call data.index(x) for each of the checks

Answer

Convert to a set once, making each check O(1) average

Why

x in some_list checks items one by one: O(n). Doing it inside a loop of n iterations costs O(n²), which is huge for a million items.

x in some_set uses hashing: O(1) on average.

Converting once costs O(n), then all checks are cheap.

Remember

Many membership checks → use a set.

Key terms

• Hash table
• Big-O notation
• Linear search
• Set
• Time complexity
• Space complexity