Complexity and Choosing Data Structures

Big-O in one table

Big-O ignores constants and describes growth, not speed. An O(n²) algorithm can beat an O(n log n) one on ten items and will lose catastrophically on a million.

Cost by container

The single most valuable change

import time
import random

blocked = [f"user{i}" for i in range(20_000)]
requests = [f"user{random.randint(0, 40_000)}" for _ in range(20_000)]

start = time.perf_counter()
allowed = [r for r in requests if r not in blocked]        # O(n * m)
print(f"list:  {time.perf_counter() - start:.3f}s")

blocked_set = set(blocked)                                  # built once, O(m)
start = time.perf_counter()
allowed = [r for r in requests if r not in blocked_set]     # O(n)
print(f"set:   {time.perf_counter() - start:.3f}s")

list:  3.8s
set:   0.004s        about a thousand times faster

Nothing else in this note comes close. Whenever a membership test sits inside a loop, convert the container to a set once, outside the loop.

Accidental quadratic behaviour

import time

data = list(range(20_000))

# O(n^2): each `in` scans the whole result list
start = time.perf_counter()
unique = []
for item in data:
    if item not in unique:
        unique.append(item)
print(f"list scan:  {time.perf_counter() - start:.3f}s")

# O(n): the set does the checking
start = time.perf_counter()
seen = set()
unique = []
for item in data:
    if item not in seen:
        seen.add(item)
        unique.append(item)
print(f"with a set: {time.perf_counter() - start:.3f}s")

# O(n), and one line
start = time.perf_counter()
unique = list(dict.fromkeys(data))
print(f"fromkeys:   {time.perf_counter() - start:.3f}s")

import time

# O(n^2): every += copies the whole string built so far
start = time.perf_counter()
text = ""
for i in range(50_000):
    text += str(i)
print(f"concatenation: {time.perf_counter() - start:.3f}s")

# O(n)
start = time.perf_counter()
text = "".join(str(i) for i in range(50_000))
print(f"join:          {time.perf_counter() - start:.3f}s")

import time
from collections import deque

# O(n^2): every pop(0) shifts the whole list
start = time.perf_counter()
values = list(range(50_000))
while values:
    values.pop(0)
print(f"list.pop(0):      {time.perf_counter() - start:.3f}s")

# O(n)
start = time.perf_counter()
values = deque(range(50_000))
while values:
    values.popleft()
print(f"deque.popleft():  {time.perf_counter() - start:.3f}s")

These three - membership in a list, string concatenation in a loop, and pop(0) - are the accidental O(n²) patterns that appear most often in real code. Each has a one line fix.

Choosing the container

from collections import deque, Counter, defaultdict

# "Do I have this?" asked repeatedly -> set
seen = set()

# "What is the value for this key?" -> dict
prices = {"pen": 10}

# "Give me item number 5" -> list
rows = ["a", "b", "c"]

# "Add and remove at both ends" -> deque
queue = deque()

# "How many of each?" -> Counter
counts = Counter(["a", "b", "a"])

# "Group these under keys" -> defaultdict(list)
groups = defaultdict(list)

# "It never changes and may be a key" -> tuple
point = (3, 7)

import time

records = [{"id": i, "name": f"user{i}"} for i in range(20_000)]
ids = list(range(0, 20_000, 100))

# Scanning the list for each lookup: O(n) per lookup
start = time.perf_counter()
for target in ids:
    match = next(r for r in records if r["id"] == target)
print(f"scan:  {time.perf_counter() - start:.4f}s")

# Build an index once: O(n) total, then O(1) per lookup
start = time.perf_counter()
index = {r["id"]: r for r in records}
for target in ids:
    match = index[target]
print(f"index: {time.perf_counter() - start:.4f}s")

Sorting

import time

data = [{"name": f"u{i}", "score": (i * 37) % 1000} for i in range(50_000)]

# Sorting once and slicing: O(n log n)
start = time.perf_counter()
top = sorted(data, key=lambda r: -r["score"])[:10]
print(f"sorted: {time.perf_counter() - start:.4f}s")

# heapq: O(n log k), much better when k is small
import heapq

start = time.perf_counter()
top = heapq.nlargest(10, data, key=lambda r: r["score"])
print(f"nlargest: {time.perf_counter() - start:.4f}s")

# The single largest: O(n), no sort at all
start = time.perf_counter()
best = max(data, key=lambda r: r["score"])
print(f"max: {time.perf_counter() - start:.4f}s")

Sorting to find the maximum is a common and expensive habit. max is linear, and heapq.nlargest handles the top few.

Sorting stability and multiple keys

records = [
    {"dept": "eng", "salary": 90}, {"dept": "design", "salary": 75},
    {"dept": "eng", "salary": 82},
]

# One pass with a tuple key
print(sorted(records, key=lambda r: (r["dept"], -r["salary"])))

# Two passes, relying on stability - same result, and slower
by_salary = sorted(records, key=lambda r: -r["salary"])
print(sorted(by_salary, key=lambda r: r["dept"]))

Binary search on sorted data

import bisect
import time

values = sorted(range(0, 1_000_000, 2))
targets = list(range(0, 1_000_000, 50_000))

start = time.perf_counter()
for target in targets:
    found = target in values                # O(n) - the list does not know it is sorted
print(f"in:     {time.perf_counter() - start:.4f}s")

start = time.perf_counter()
for target in targets:
    index = bisect.bisect_left(values, target)
    found = index < len(values) and values[index] == target
print(f"bisect: {time.perf_counter() - start:.4f}s")

import bisect

scores = [0, 40, 60, 75, 90]
grades = ["F", "D", "C", "B", "A"]


def grade(score):
    return grades[bisect.bisect_right(scores, score) - 1]


for score in [0, 39, 40, 74, 95]:
    print(score, grade(score))

Space and time trade offs

import time
from functools import cache


def slow_fib(n):
    return n if n < 2 else slow_fib(n - 1) + slow_fib(n - 2)


@cache
def fast_fib(n):
    return n if n < 2 else fast_fib(n - 1) + fast_fib(n - 2)


start = time.perf_counter()
slow_fib(30)
print(f"no cache: {time.perf_counter() - start:.3f}s")

start = time.perf_counter()
fast_fib(30)
print(f"cached:   {time.perf_counter() - start:.6f}s")

Memory

import sys

print(sys.getsizeof(list(range(1000))))          # about 8 KB
print(sys.getsizeof(tuple(range(1000))))         # slightly less
print(sys.getsizeof(set(range(1000))))           # more - hash table overhead
print(sys.getsizeof(range(1000)))                # 48 bytes, whatever the size
print(sys.getsizeof((n for n in range(1000))))   # about 200 bytes

import sys


class WithDict:
    def __init__(self, x, y):
        self.x, self.y = x, y


class WithSlots:
    __slots__ = ("x", "y")

    def __init__(self, x, y):
        self.x, self.y = x, y


a, b = WithDict(1, 2), WithSlots(1, 2)
print(sys.getsizeof(a) + sys.getsizeof(a.__dict__))
print(sys.getsizeof(b))

Analysing your own code

def find_duplicates(items):
    """What is the complexity of this?"""
    duplicates = []
    for i in range(len(items)):                # n iterations
        for j in range(i + 1, len(items)):     # n iterations
            if items[i] == items[j]:           # O(1)
                duplicates.append(items[i])
    return duplicates
# Two nested loops over the same data -> O(n^2)


from collections import Counter


def find_duplicates_fast(items):
    counts = Counter(items)                    # O(n)
    return [item for item, count in counts.items() if count > 1]     # O(n)
# O(n)

• A loop over the input: multiply by n.
• Nested loops over the same input: n².
• Halving the input each step: log n.
• A sort: n log n.
• A dictionary or set operation inside a loop: still n, not n².
• Keep only the largest term; O(n² + n) is O(n²).

Common mistakes

• Testing membership against a list inside a loop.
• Building a string with += in a loop.
• Using list.pop(0) or insert(0, x) repeatedly.
• Sorting to find one maximum.
• Rebuilding an index inside the loop that uses it.
• Choosing a container by habit rather than by the operation performed most.
• Optimising constants while an O(n²) algorithm sits untouched.

Best practices

• Pick the container from the operation you do most, not the one you know best.
• Convert to a set or build an index once, before the loop.
• Use join for strings and deque for queues.
• Use max, min and heapq.nlargest instead of sorting.
• Cache pure, repeatedly called functions with functools.cache.
• Fix the algorithm before touching the constants.

Practice

1. Time membership tests against a list and a set of 100 000 items.
2. Rewrite an accidentally quadratic deduplication as a linear one.
3. Turn a repeated linear search over records into a dictionary index and measure it.
4. Find the top five items three ways - sort, nlargest, a manual loop - and compare.
5. Work out the complexity of three functions in your own code.

Conclusion

Complexity decides how a program behaves as data grows; the container decides the complexity. A set instead of a list, a dictionary index instead of a scan, join instead of +=, and a deque instead of pop(0) will outperform any amount of line by line tuning.