Free lessons · from Think in Patterns
Big-O and Python at a glance
Two tables to keep open while you solve: what each complexity means in practice, and what Python’s built-ins cost. The second is where most “my O(n) solution timed out” surprises come from.
Big-O, with n = 10⁵
| Complexity | Steps for n = 10⁵ | Feels like | Typical source |
|---|---|---|---|
| O(1) | 1 | instant | hash lookup, array index, arithmetic |
| O(log n) | 17 | instant | binary search, heap push and pop, balanced tree |
| O(n) | 10⁵ | instant | one pass, two pointers, sliding window, BFS and DFS |
| O(n log n) | 1.7 × 10⁶ | well under a second | sorting, n heap operations, divide and conquer |
| O(n²) | 10¹⁰ | minutes: too slow | nested loops over the input, naive pairs |
| O(2ⁿ) | astronomical | only for n ≤ 20 | all subsets, naive recursion without memoisation |
| O(n!) | astronomical | only for n ≤ 10 | all permutations |
log means log₂, the number of halvings (log₂ 10⁵ ≈ 17). The base never changes the Big-O class: logs in different bases differ only by a constant factor, which Big-O ignores.
Dropping a log is rarely worth extra code; dropping a factor of n always is. And an O(n) hash map is the usual price for turning O(n²) into O(n).
What Python’s built-ins cost
| Operation | Cost | Note |
|---|---|---|
lst[i], lst[i] = x, len(lst) | O(1) | |
lst.append(x), lst.pop() | O(1) | at the end only |
lst.pop(0), lst.insert(0, x) | O(n) | shifts everything; use collections.deque |
x in lst, lst.index(x), lst.remove(x) | O(n) | the classic hidden O(n²) inside a loop |
lst[a:b] | O(b − a) | copies; slicing inside a loop is a cost |
sorted(lst), lst.sort() | O(n log n) | Timsort; O(n) on already-sorted input |
min(lst), max(lst), sum(lst) | O(n) | inside a loop this is O(n²) |
x in a_set, x in a_dict, d[k], d[k] = v | O(1) average | hashing; worst case O(n) is not an interview concern |
d.keys(), d.items() iteration | O(n) | |
deque.append / appendleft / pop / popleft | O(1) | the queue for BFS and sliding windows |
heapq.heappush / heappop | O(log n) | a min-heap; Python 3.14 adds heappush_max / heappop_max, and pushing -x works on every version |
heapq.heapify(lst) | O(n) | faster than n pushes |
heapq.nlargest(k, xs) | O(n log k) | |
bisect.bisect_left(sorted_xs, x) | O(log n) | position only; inserting is still O(n) |
s + t for strings | O(len(s) + len(t)) | strings are immutable: build with a list and "".join |
"".join(parts) | O(total length) | |
s[::-1], s.split(), s.lower() | O(n) | |
str(n), int(s) | O(digits) |
Snippets worth memorising
from collections import Counter, defaultdict, deque
freq = Counter(nums) # value -> count
groups = defaultdict(list) # key -> list, missing keys start empty
freq.most_common(k) # the k most frequent (value, count) pairsimport heapq, bisect
heapq.heappush(h, (priority, item)) # tuples compare field by field
smallest = heapq.heappop(h)
i = bisect.bisect_left(sorted_xs, x) # first index with sorted_xs[i] >= xfrom functools import lru_cache
@lru_cache(maxsize=None)
def f(i, j): # arguments must be hashable
...Python traps in interviews
- Recursion depth is about 1 000 by default. Deep recursion (a 10⁵-node linked list or tree spine) needs
sys.setrecursionlimit(10**6)or an iterative version. Say which you chose. - Integer division:
7 // 2is3,-7 // 2is-4(rounds toward minus infinity). When the problem wants truncation toward zero,int(a / b)works while the numbers stay below 2⁵³ (any 32-bit limit is fine), because/goes through a float. For integers of any size:q = abs(a) // abs(b), thenq = -qif exactly one ofaandbis negative. - Mutable default arguments (
def f(path=[])) keep state between calls. UseNoneand create inside. - Copying:
b = aaliases a list;b = a[:]orlist(a)copies one level; nested lists needcopy.deepcopy. - Big integers never overflow in Python, so “handle 32-bit overflow” problems need explicit checks against 2³¹ − 1.
for i in range(len(xs))when you need the index;enumerate(xs)when you need both; never modify a list while iterating over it.- Tuples, not lists, as dict keys and in sets. Lists are unhashable.
This is page 111 of Think in Patterns. Every one of its 340 problems states the cost of each approach and why, and the 13 Foundations topics start Big-O from zero.