Big-O Reasoning for Python Collections
Complexity is a way to compare growth
Big-O describes how the work or memory of an operation grows with input size. It helps you reject the wrong data structure before profiling, but it does not replace measurement: constant factors, allocation, cache locality, input distribution, and I/O can dominate a real service.
For Python interviews, start by naming the operation and the representation. “Dictionary lookup is O(1)” is incomplete; it is average O(1) lookup in a hash table, assuming a hashable key and ordinary collision behavior.
The collection operations worth knowing
| Collection | Useful operation | Typical complexity | Why |
|---|---|---|---|
list | append | amortized O(1) | occasional resize copies elements |
list | membership / search | O(n) | scans elements in order |
list | insert or remove at front | O(n) | shifts remaining elements |
dict / set | lookup, insert, delete | average O(1) | hash-table probe |
dict / set | iterate all items | O(n) | each item must be visited |
deque | append/pop either end | O(1) | optimized double-ended structure |
These are operational models, not an excuse to ignore the size of values or the cost of equality and hashing for custom objects.
Avoid accidental quadratic work
A common bug is doing a linear membership scan inside another loop. Precompute the membership structure once.
requested_ids = ["u-1", "u-2", "u-3"]
blocked_ids = fetch_blocked_ids() # perhaps thousands of IDs
# O(len(blocked_ids)) once, then average O(1) per check
blocked = set(blocked_ids)
allowed = [user_id for user_id in requested_ids if user_id not in blocked]Converting inside the loop defeats the optimization:
# Do not do this: rebuilds a set for every requested ID.
# allowed = [user_id for user_id in requested_ids if user_id not in set(blocked_ids)]State the total cost in an interview. Building the set is O(m); checking n requests is average O(n), for average O(n + m) time and O(m) extra memory.
Amortized analysis explains list.append
Most append calls write into available capacity. When the underlying array is full, Python allocates a larger one and copies references, which is O(n) for that append. Because resizes are infrequent, a long sequence of appends is amortized O(1) each.
This is why appending in a loop is normally good, while repeatedly concatenating immutable strings is often not. Still, use a benchmark when the workload is large or performance-sensitive.
Pick for the access pattern, not the label
from collections import deque
queue = deque(["job-1", "job-2"])
queue.append("job-3")
next_job = queue.popleft() # O(1)Using list.pop(0) creates an O(n) shift. Conversely, a deque is not a substitute for a list when you need fast indexed access or slicing. The data structure should match the dominant operation and memory constraints.
A senior-level answer includes the workload
Ask how many items arrive, whether keys are adversarial, whether order matters, and whether extra memory is acceptable. Then explain a baseline and the measured threshold for changing it. Complexity informs that decision; production evidence confirms it.