Space Complexity
Space complexity measures the extra memory an algorithm holds while it runs, against n, leaving out the input itself. A running total holds 1 number however many rows go past: O(1) space. A set of every distinct id seen holds up to n entries: O(n). A table of every pair of rows holds n² cells.
| Task | Extra memory | Time |
|---|---|---|
| Sum a column | O(1): 1 running total | O(n) |
| Remove duplicate ids with a set | O(n): 1 entry per distinct id | O(n) |
| Remove duplicates by comparing pairs | O(1) | O(n²) |
| Sort, then compare neighbours | O(n): sorted() returns a new list | O(n log n) |
| Join through a dict of 1 side | O(m): 1 entry per key on that side | O(n + m) |
Rows 2 and 3 solve the same problem from opposite ends: the set spends memory to save time, and the pairwise loop spends time to save memory. The program below runs both on 8 ids.
ids = [7, 3, 7, 9, 3, 3, 12, 9]
pair_checks = 0
dupes_slow = 0
for i in range(len(ids)):
for j in range(i):
pair_checks += 1
if ids[i] == ids[j]:
dupes_slow += 1
break
seen = set()
dupes_fast = 0
for x in ids:
if x in seen:
dupes_fast += 1
seen.add(x)
print("pairwise:", dupes_slow, "dupes,", pair_checks, "checks, 0 extra values")
print("set: ", dupes_fast, "dupes,", len(ids), "checks,", len(seen), "extra values")Output:
pairwise: 4 dupes, 19 checks, 0 extra values set: 4 dupes, 8 checks, 4 extra values
On 8 ids that is 19 checks against 8. On 10,000,000 distinct ids the pairwise loop needs about 50 trillion checks, while the set needs 10,000,000 checks and room for 10,000,000 entries.
The dict join: memory bought, time saved
Joining orders to customers with nested loops compares every order with every customer: O(n × m) time and no extra memory. Building a dict keyed by customer id first costs 1 pass over the customers and memory for m entries; after that, each order finds its customer in 1 lookup, O(n + m) overall.
customers = [("c1", "Ana"), ("c2", "Ben"), ("c3", "Chen")]
orders = [("o1", "c2", 40), ("o2", "c1", 15), ("o3", "c2", 25), ("o4", "c3", 60)]
name_by_id = {}
for customer_id, name in customers:
name_by_id[customer_id] = name
joined = []
for order_id, customer_id, amount in orders:
joined.append((order_id, name_by_id[customer_id], amount))
print(joined)[('o1', 'Ben', 40), ('o2', 'Ana', 15), ('o3', 'Ben', 25), ('o4', 'Chen', 60)]
Scale the join to 50,000,000 orders and 2,000,000 customers and the 2 approaches land far apart:
- 100 trillion
- 52 million
When memory runs out first
The dict join holds up only while the dict fits in memory. At 100 bytes per entry, 2,000,000 customers need about 200 MB, which a laptop holds, and 2,000,000,000 distinct ids need about 200 GB, which most single machines do not. When the lookup side outgrows memory, shrink it before giving up the speed.
- Do
- Build the lookup dict from the smaller side of a join
- Keep only the fields the lookup needs as dict values
- Process 1 date partition at a time when a year of keys won't fit
- Keep a running total when the total is all the job reports
- Avoid
- Collect every row into a list when 1 running value answers the question
- Build a table of every pair for a million rows
- Assume a set of ids fits in production because it fit on a sample
- Swap a dict for nested loops to save memory without doing the time math
A job attaches campaign names to 80 million click rows. The campaigns table has 5,000 rows. How should the join be built?
- Build a dict from the clicks and look up each campaign in it
- Use nested loops so the job holds no extra memory at all
- Build a dict from the campaigns and look up each click in it
- Either side works, since a dict join is O(n + m) either way
Build the dict once, outside the loop
The dict saves time only when it is built once, before the loop over orders, and read inside it. The version below prints the same pairs and keeps no dict, but each order scans the customer list again, the nested-loop cost from earlier: with 50,000,000 orders and 2,000,000 customers, 100 trillion comparisons. Building the dict inside the order loop is the same trap in another form, since each order then rebuilds all m entries for 1 lookup.
for order_id, customer_id, amount in orders:
for cid, country in customers:
if cid == customer_id:
print(order_id, country)One edge case remains in the fast version: an order whose customer_id is missing from the dict stops the run with a KeyError at name_by_id[customer_id]. Reading it with name_by_id.get(customer_id) returns None for that order instead, at the same cost of 1 lookup.
About this lesson
This section is part of the Complexity: Intermediate lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.