Complexity: Intermediate
The number of reads is the number of times n can be halved before 1 item is left. That count is the base-2 logarithm of n, written log n, and an algorithm whose work grows this way is O(log n). The practical reading: doubling the input adds 1 read.
| Sorted items (n) | Linear scan, worst case | Halving search, worst case |
|---|---|---|
| 16 | 16 reads | 5 reads |
| 1,000 | 1,000 reads | 10 reads |
| 1,000,000 | 1,000,000 reads | 20 reads |
| 1,000,000,000 | 1,000,000,000 reads | 30 reads |
Watching the range shrink
The program below is binary search. It keeps 2 boundaries, lo and hi, around the slice of the list that could still hold the target. Each pass of the while loop reads the item at mid, halfway between them, and moves 1 boundary past it. Follow the gap between the boundaries: 16 candidates, then 8, then 4, then 1.
user_ids = [103, 118, 127, 140, 152, 166, 171, 189,204, 215, 233, 247, 251, 268, 279, 295]target = 251lo = 0hi = len(user_ids) - 1checks = 0found_at = Nonewhile lo <= hi:mid = (lo + hi) // 2checks += 1print(f"check {checks}: index {mid} holds {user_ids[mid]}")if user_ids[mid] == target:found_at = midbreakif user_ids[mid] < target:lo = mid + 1else:hi = mid - 1print(f"found at {found_at} after {checks} checks")
16 sorted ids, 4 middle reads to find 251.
Why an index makes a lookup fast
A table stores rows in the order they arrived. A query for user 251's plays cannot know where those rows sit, so it reads every row and checks user_id on each: O(n). An index on user_id is a second structure holding that column's values in sorted order, each paired with the position of the row it came from. The engine halves its way through the sorted values to the first 251, then follows the stored positions back to the rows.
| row | user_id | track_id |
|---|---|---|
| 0 | 233 | t_9081 |
| 1 | 118 | t_1270 |
| 2 | 251 | t_4412 |
| 3 | 140 | t_0335 |
| 4 | 233 | t_7720 |
| 5 | 189 | t_1270 |
| user_id | row |
|---|---|
| 118 | 1 |
| 140 | 3 |
| 189 | 5 |
| 233 | 0 |
| 233 | 4 |
| 251 | 2 |
while loop run over an unsorted list still returns an answer, often a wrong one, with no error. A database keeps each index sorted on every insert and update, which is why each extra index slows down writes.An events table is indexed on user_id. It grows from 10 million rows to 40 million. How does the work of an indexed lookup for a single user_id change?
Why the boundary moves past mid
Once user_ids[mid] has been read and is not the target, index mid is ruled out, so the next range has to leave it behind. The update lo = mid keeps it in, and that breaks the loop. Search the 16 ids for 300, larger than all of them: the boundaries close in until lo is 14 and hi is 15. Then mid is 14, 279 is smaller than 300, and lo = mid sets lo to 14 again. Every later pass computes the same mid, reads the same id and makes the same move, so the loop never ends. The update lo = mid + 1 shrinks the range by at least 1 item per pass, and the trace below shows it stopping after 5 reads.
| Pass | lo | hi | mid | Id read | Next move |
|---|---|---|---|---|---|
| 1 | 0 | 15 | 7 | 189 | lo = 8 |
| 2 | 8 | 15 | 11 | 247 | lo = 12 |
| 3 | 12 | 15 | 13 | 268 | lo = 14 |
| 4 | 14 | 15 | 14 | 279 | lo = 15 |
| 5 | 15 | 15 | 15 | 295 | lo = 16 |
| 6 | 16 | 15 | not computed | none | lo > hi, loop ends, found_at stays None |
No single look at a row tells you where it belongs in sorted order, so sorting needs more than 1 pass. The general-purpose sorts in wide use, including the merge-based algorithm behind Python's sorted(), cost O(n log n). Merge sort shows where that comes from: treat each item as a sorted run of 1, then merge neighbouring runs into sorted runs twice as long, round after round. Every round touches all n items, and run length doubles each round, so after log n rounds a single run remains.
data = [52, 17, 88, 3, 41, 29, 70, 9]runs = []for x in data:runs.append([x])level = 0while len(runs) > 1:merged_runs = []for i in range(0, len(runs), 2):left = runs[i]right = runs[i + 1]out = []a = 0b = 0while a < len(left) and b < len(right):if left[a] <= right[b]:out.append(left[a])a += 1else:out.append(right[b])b += 1out = out + left[a:] + right[b:]merged_runs.append(out)runs = merged_runslevel += 1print("level", level, runs)
8 values, 3 rounds, every round writes all 8.
The 8 values took 3 rounds of 8 moves each, 24 moves in total, and that is the whole shape of n log n: log n passes over the data.
| Rows (n) | n | n log n | n² |
|---|---|---|---|
| 1,000 | 1,000 | about 10,000 | 1,000,000 |
| 1,000,000 | 1,000,000 | about 20 million | 1 trillion |
| 1,000,000,000 | 1 billion | about 30 billion | 1 quintillion |
Window functions sort inside each partition
SQL ranks rows within groups through a window function. The query below numbers each user's tracks from most played to least: PARTITION BY user_id splits the rows into 1 group per user, ORDER BY play_count DESC sorts each group, and ROW_NUMBER() counts 1, 2, 3 down each sorted group.
Rows move left to right; only the sort step grows faster than the row count.
A group of k rows costs about k log k to sort, so the window's total is that cost summed over the groups. Smaller groups shrink the log: sorting 1,000 groups of 1,000 rows pays about 10 per row, while a window with no PARTITION BY sorts the whole table as a single group and pays log n per row.
- ▸
sorted()and.sort()in Python code - ▸
ORDER BYon a query's output - ▸A window function with
ORDER BY, paid once per partition - ▸Removing duplicates by sorting, then comparing neighbours
- ▸Sorting a whole table to keep its top 10 rows
A nightly job sorts 2 million rows in 4 seconds. Next quarter the table holds 4 million rows. About how long should the sort take?
Sorting each group in Python
Python code ranks within groups the same way: keep a dict that maps each user_id to a list of that user's rows, and sort each list on its own. The cost follows the SQL window, about k log k per list of k rows, added up across users. sorted() calls its key function once per item before it compares anything, so a key that reads 1 field adds n calls to the sort, far fewer than its n log n comparisons. reverse=True puts the largest key first, the job DESC does inside the window.
A single Big O quoted for an algorithm is usually the worst case, the bound the code can promise on every input. Hash lookups are the common exception: the O(1) quoted for a dict or set lookup is an average, and so is the O(n + m) of a join built on one. Best cases matter for a different reason: they explain how a job that ran in seconds on test data crawls on production data, whose inputs land on the slow path.
| Operation | Best case | Average case | Worst case |
|---|---|---|---|
| x in some_list | O(1): x is first | O(n): about n/2 reads | O(n): x is missing |
| Halving search, sorted list | O(1): x is in the middle | O(log n) | O(log n) |
| sorted() | O(n): input already in order | O(n log n) | O(n log n) |
| Pair check inside each group | O(n): every group has 1 row | depends on group sizes | O(n²): all rows in 1 group |
Skew: when 1 key holds most of the rows
| Users | Rows | Pair checks |
|---|---|---|
| 1,000 users | 1,000 each | 1,000,000 each |
| Total | 1,000,000 | 1 billion |
| Users | Rows | Pair checks |
|---|---|---|
| 1 bot account | 500,000 | 250 billion |
| 999 users | about 500 each | about 250,000 each |
| Total | 1,000,000 | about 250.25 billion |
Both spreads average 1,000 rows per user, so the average hides the trouble. Skew is a worst case the data chooses for you: a bot account, a default value such as an empty string, or every row with a missing key landing in the same None group.
Measuring skew in a single pass
is_new runs once for every incoming row. Which batch of incoming ids makes it do the most comparisons in total?
Guarding a quadratic step
| Batch | Keys | Rows | Average per key | Largest key | Pair checks |
|---|---|---|---|---|---|
| A | 10 | 1,000 | 100 | 100 | 100,000 |
| B | 100 | 999 | 9.99 | 900 | 810,099 |
| 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) |
The dict join: memory bought, time saved
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] = namejoined = []for order_id, customer_id, amount in orders:joined.append((order_id, name_by_id[customer_id], amount))print(joined)
The dict holds 1 entry per customer; each order then costs 1 lookup.
When memory runs out first
- 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
- 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 the dict once, outside the loop
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.
checks = ["nulls", "dupes", "schema"]combos = [[]]for check in checks:with_check = []for combo in combos:with_check.append(combo + [check])combos = combos + with_checkprint(check, "->", len(combos), "combinations")print(combos)
Each new item copies every existing combination once, with the item added.
| Items (n) | Combinations (2ⁿ) | Time at 1 million per second |
|---|---|---|
| 10 | 1,024 | about 1 millisecond |
| 20 | 1,048,576 | about 1 second |
| 30 | 1,073,741,824 | about 18 minutes |
| 40 | 1,099,511,627,776 | about 13 days |
| 50 | 1,125,899,906,842,624 | about 36 years |
Brute force on a backfill window
- ▸Keep n small: up to about 20 items, 2ⁿ stays near a million and brute force is fine
- ▸Prune: stop extending a combination once its total already runs over the limit
- ▸Use a shortcut rule, such as taking the longest job that still fits, and accept a good answer
- ▸Watch for orderings too: n items have n! orders, and 10 items already have 3,628,800
A script checks every combination of 25 candidate data sources and takes 30 seconds. A teammate adds 2 more sources. About how long will it take now?
The line that doubles the list
One line in the combination loop does the doubling: combos = combos + with_check. The old list holds every combination without the new item, and with_check holds a copy of each one with the item added, so the new list is twice as long. Drop the old half and write combos = with_check, and every combination that leaves the item out is lost: the count stays at 1 however many items arrive. The table follows the 3 checks from the animation.
| After adding | Without the item | With the item | Total |
|---|---|---|---|
| nulls | [] | [nulls] | 2 |
| dupes | [], [nulls] | [dupes], [nulls, dupes] | 4 |
| schema | the 4 combinations so far | 4 copies with schema added | 8 |
> Picture the Wrapped ranking job imagined at the start of the lesson on its single night: it reads a year of plays, counts plays per listener and track, ranks each listener's tracks, attaches track titles from the catalog, and builds the cards each listener sees.
Halving, sorting, skew, memory and doubling: the growth rates that decide whether a pipeline finishes.
- Category
- Python
- Difficulty
- intermediate
- Duration
- 20 minutes
- Challenges
- 17 hands-on challenges
Topics covered: O(log n): Logarithmic Time, O(n log n): Quasilinear Time, Best, Worst, and Average Case, Space Complexity, Exponential Time
Lesson Sections
- O(log n): Logarithmic Time
A linear scan answers "is 251 in this list?" by reading items until it meets 251 or runs out, so a list twice as long can cost twice the reads. A sorted list allows a different move. Read the middle item. If it is smaller than 251, everything to its left is smaller too, and the whole left half is discarded in 1 step; if it is larger, the right half goes instead. Each read cuts the remaining range in half, and the search stops when the range holds the target or holds nothing. Watching the range s
- O(n log n): Quasilinear Time
The middle column sits far closer to n than to n². At 1,000,000 rows a sort does about 20 passes' worth of work, while comparing every pair does 1,000,000 passes' worth, which is why a nightly sort of a billion rows is routine and an all-pairs comparison of the same rows never finishes. Window functions sort inside each partition Partitioning by user halved the predicted work, because log 1,000 is half of log 1,000,000. Sorting each group in Python
- Best, Worst, and Average Case
Two inputs of the same size can cost very different amounts. Searching a list for an id stops at the first match: if the id sits at index 0, that takes 1 comparison, the best case. A missing id gets compared with every item, the worst case. If the id is equally likely to sit anywhere, the search stops about halfway on average. Skew: when 1 key holds most of the rows Pipelines often split work by key: per user, per country, per day. A linear per-key step costs the same however rows spread across
- 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. 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. On 8 ids that is 19 check
- Exponential Time
Some questions ask which combination of items is best: which sources to backfill tonight, which checks fit inside a time budget. Each item is in the combination or out of it, so 1 item gives 2 choices, 2 items give 2 × 2 = 4, and n items give 2ⁿ. Code that tries every combination does O(2ⁿ) work. The list doubled with every item. That is the signature of exponential time: O(n²) quadruples when n doubles, while O(2ⁿ) doubles when n grows by 1. Brute force on a backfill window A backfill window ha