Complexity and Python: know what the tool does

Choosing the right container usually helps more than shortening a line. Are you looking something up, counting, processing in order, or repeatedly extracting a minimum?

1. Complexity isn't a count of loops

A while inside a for isn't automatically O(n²). If both pointers only advance, each moves at most n times: O(n) overall. Conversely, one loop copying values[:index] each time copies 0, 1, …, n−1 elements in turn, O(n²) in total.

We assume constant-cost integer operations and comparisons. Very large integers, long strings, and tuple keys require accounting for arithmetic, comparison, and hashing lengths.

2. Average and amortized are different

• Average / expected: dict lookup is usually O(1) under hashing assumptions. Extreme collisions can make it O(n).
• Amortized: an individual list.append can trigger an expensive resize, but a long sequence costs O(1) per append amortized.

Consider a toy dynamic array that doubles its capacity when full: 1, 2, 4, 8. Count one operation to write a new element and one for each existing element copied during a resize.

The fifth append is expensive, but all eight together cost just 15 operations. As the array grows, copying costs $1+2+4+\cdots$; including new writes, the total remains O(n). Amortized analysis needs no random-input assumption and isn't an average of benchmark timings. Doubling is our teaching model, not CPython's actual growth schedule.

def doubling_append_costs(count):
    capacity = 0
    costs = []
    for size in range(count):
        cost = 1
        if size == capacity:
            cost += size
            capacity = max(1, capacity * 2)
        costs.append(cost)
    return costs


assert doubling_append_costs(8) == [1, 2, 3, 1, 5, 1, 1, 1]
assert sum(doubling_append_costs(8)) == 15

A hash table's usual O(1) lookup relies on assumptions about hash distribution instead: many colliding keys can make lookup slow. Resizing the table also has an amortized cost, but that is a separate argument, not a guarantee of fast individual lookups.

Normally exclude input space, include extra containers and recursion frames, and report output storage separately when it dominates.

3. Container cheat sheet

These bounds describe usual Python implementations with the assumptions above. Official APIs: dict / set, deque / Counter, heapq, bisect.

Tail pop() needn't shift later elements, but can occasionally shrink the backing array. That's why it is also marked amortized: see CPython 3.12's list_pop_impl and list_resize. The usual cheap operation isn't a fixed-latency guarantee.

4. Functions you'll actually use

from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect_right
import heapq

counts = Counter("banana")
groups = defaultdict(list)
groups["fruit"].append("pear")
queue = deque(["start"])
queue.append("next")
first = queue.popleft()
values = [1, 2, 2, 5]
left = bisect_left(values, 2)
right = bisect_right(values, 2)
heap = [5, 1, 3]
heapq.heapify(heap)
smallest = heapq.heappop(heap)

Results: counts['a'] == 3, first == 'start', left == 1, right == 3. The count of 2 is right-left == 2; smallest == 1.

enumerate(values) supplies index and value; zip(first, second) stops at the shorter input by default; sorted(values, key=...) returns a new list; values.sort() mutates and returns None. Negating numeric priorities gives a max-heap on older Python versions. Python 3.14 also exposes heapify_max, heappush_max, and heappop_max; check the runtime first.

5. Recursion, slices, and outputs use space too

A tree shaped like a chain can need n recursive frames even without an explicit list: O(n) stack space. Only a balanced binary tree guarantees O(log n) height.

values[left:right] copies that slice; ''.join(parts) allocates the output string. “In place” doesn't always mean O(1) auxiliary space: sorting may still use temporary storage internally.

6. Close the notes and try

Next: Hash maps: what should you remember?.