PART 4 · DSA AND COMPLEXITY · CHAPTER 16

Time vs space trade-offs

FreeLesson 41 of 78

Most "optimise this" questions are a trade: spend memory to save time, or spend time to save memory. Say which one you are making and why.

THREE WAYS TO ANSWER "IS THIS ID PRESENT?"PYTHON 3.12

import sys, time, bisect

ids = list(range(0, 2_000_000, 2))          # 10 lakh sorted ids
targets = list(range(0, 2_000_000, 2_001))  # 1,000 lookups

def bench(fn):
    t = time.perf_counter(); fn(); return (time.perf_counter() - t) * 1000

as_set = set(ids)
lst = bench(lambda: [t in ids for t in targets])
st = bench(lambda: [t in as_set for t in targets])
bs = bench(lambda: [ids[bisect.bisect_left(ids, t)] == t for t in targets])

kb = lambda obj: sys.getsizeof(obj) // 1024
print(f"list scan {lst:8.1f} ms   memory {kb(ids):>6} KB")
print(f"set       {st:8.2f} ms   memory {kb(as_set):>6} KB")
print(f"bisect    {bs:8.2f} ms   memory      0 KB extra")

Output

list scan   8504.1 ms   memory   7812 KB
set           0.71 ms   memory  32768 KB
bisect        2.11 ms   memory      0 KB extra

The times are what this run measured when the book was built. Yours will differ.

PRECOMPUTE ONCE, ANSWER FAST FOREVER: PREFIX SUMSPYTHON 3.12

from itertools import accumulate

daily = [0, 1999, 0, 0, 846, 0, 0, 2397, 0, 1598]
prefix = [0, *accumulate(daily)]          # O(n) once, O(n) memory

def range_sum(i, j):                      # O(1) per question
    return prefix[j + 1] - prefix[i]

print(prefix)
print(range_sum(1, 4), range_sum(0, 9), sum(daily[1:5]))

Output

[0, 0, 1999, 1999, 1999, 2845, 2845, 2845, 5242, 5242, 6840]
2845 6840 2845

Summing a range by hand costs O(k) every time you ask. One O(n) pass to build the prefix array makes every later question O(1). Worth it when the same data is queried many times.

Problem	Spend memory for speed	Spend time to save memory	Pick the cheaper-memory side when
Is x present?	set: O(1) lookup, O(n) memory	sort + bisect: O(log n), no extra	Data is already sorted or memory is tight
Find duplicates	set in one pass: O(n) / O(n)	sort then compare neighbours: O(n log n) / O(1)	You may modify the input
Top k of n	sort all: O(n log n) / O(n)	size-k heap: O(n log k) / O(k)	n is huge or streamed
Many range sums	prefix array: O(1) per query	loop per query: O(k)	Only a few queries
Repeat lookups	cache results (lru_cache)	recompute each time	Inputs rarely repeat
Join two files	hash join: O(n + m), small side in RAM	sort-merge join: O(n log n), streams	Neither side fits in memory
Process a file	load it all: fast, O(n) RAM	stream rows: O(1) RAM	Almost always in DE

Practice before you move on

Precompute a dict from customer_id to name using customers.json, then answer five lookups from it.
Use bisect on the sorted amounts of orders.csv to count the orders above 1,000.