03. Time Complexity of Built-in Types
Picking the right container is often the difference between AC and TLE. Learn the average-case time complexity of every common operation on list, deque, set, and dict.
What you'll learn
- 1List the time complexity of common operations on list, deque, set, dict
- 2Choose set/dict over list for fast membership checks
- 3Choose deque over list for queue-like operations
Overview
A Python list is a dynamic array, a deque is a doubly-linked deque, a set is a hash set, and a dict is a hash table. Each has different costs per operation. Knowing the table below will save you hours of debugging mysterious TLEs.
Core Concepts
1. list (dynamic array)
| Operation | Avg. complexity | Notes |
|---|---|---|
| list[i] / list[i] = x | O(1) | Random access |
| list.append(x) | O(1) amortized | Most common ops |
| list.pop() | O(1) | From the end |
| list.pop(0) / list.insert(0, x) | O(n) | From the front โ avoid in hot loops! |
| x in list | O(n) | Linear scan |
| list.sort() | O(n log n) | Timsort |
| list[a:b] | O(b-a) | Copies the slice |
2. collections.deque (double-ended queue)
| Operation | Complexity |
|---|---|
| append(x) / appendleft(x) | O(1) |
| pop() / popleft() | O(1) |
| deque[i] | O(n) โ random access is slow! |
| x in deque | O(n) |
Use deque whenever you push/pop at the front. Use list when you need random access by index.
3. set (hash set)
| Operation | Avg. complexity |
|---|---|
| x in set | O(1) |
| set.add(x) / set.remove(x) | O(1) |
| A | B / A & B / A - B | O(|A| + |B|) |
| len(set) | O(1) |
4. dict (hash map)
| Operation | Avg. complexity |
|---|---|
| dict[key] | O(1) |
| dict[key] = v | O(1) |
| key in dict | O(1) |
| del dict[key] | O(1) |
| dict.keys() / .values() / .items() | O(1) (view object) |
Examples
Example 1 โ src/01_list_vs_deque.py
Insert at the front 10,000 times. list O(nยฒ) vs deque O(n) โ the difference is dramatic.
Example 2 โ src/02_in_list_vs_set.py
Membership check `x in container` for 100,000 lookups. list O(n) vs set O(1).
Example 3 โ src/03_dict_counting.py
Counting frequencies with dict.get vs collections.Counter.
Example 4 โ src/04_set_operations.py
Set algebra: union, intersection, difference.
Common Mistakes
- Calling list.insert(0, x) or list.pop(0) repeatedly โ switch to a deque.
- Doing `if x in big_list:` in a loop โ convert big_list to a set first.
- Using deque[i] for random access โ use list.
- Iterating dict.keys() to find a value โ invert the dict instead.
- Forgetting Python set/dict use *average* O(1) โ worst case is O(n) with hash collisions (rare in practice).
Recap
- list = dynamic array (great for random access, slow at front).
- deque = fast at both ends (slow for random access).
- set/dict = O(1) lookup (use them for membership and counting).
- Pick the right container before worrying about your algorithm.
Try It
- Take a solution that times out and check whether any container choice is wrong.
- Solve BOJ 1764 (Listen & See) using set intersection.
All lecture materials and example code are openly available on GitHub.
View on GitHub โ