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, O(n) grows in step with it.
| Operation | list | dict / set |
|---|---|---|
x in c | O(n) scan | O(1) |
| get by index / key | O(1) | O(1) |
| append / add | O(1) | O(1) |
| insert or pop at front | O(n) shift | (use deque, lesson 6-1) |
| find by value | O(n) | O(1) |
The headline: membership tests on a list scan every element; 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 storage 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-in inside one loop over the same data means O(n²), the classic accidental slowdown. Converting the lookup side to a set is often the whole fix.
Code exercise · python
Run this program. Same answers, but the set version does about 100,000 times less work per lookup. We time both and print who won.
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.
Code exercise · python
Your turn. find_duplicates currently uses a list called seen, making it O(n²). Keep the exact same output but make seen a set, and add to it with seen.add(...).
Quiz
Checking `x in xs` where xs is a 1,000,000-item LIST does roughly how much work in the worst case?
Problem
A loop runs over n items, and inside it does a membership check on a SET. In big-O terms, what is the total cost? Answer like O(n), O(n²), or O(n log n).