In Module 2 we learned to measure algorithms: we can compute their time cost, their memory consumption, and tell the best case from the worst. But measuring is not creating. When the RutaBus team faces a new problem — finding a line's rush hour, detecting the two stops closest to each other — it needs more than a stopwatch: it needs design strategies, proven patterns for building algorithms from scratch. This lesson opens Module 3 with the first and perhaps most elegant of the four great strategies we previewed in 01-02: divide and conquer. The idea is deceptively simple — split the problem into pieces, solve each piece, and reassemble the solution — but from it were born some of the most efficient algorithms ever written.
Contents
- The general scheme: divide, conquer, combine
- When it applies (and when it doesn't)
- First RutaBus example: a line's rush hour
- Second RutaBus example: the closest pair of stops in 1D
- Reasoning about cost: counting levels of division
- Famous algorithms of the strategy
The general scheme: divide, conquer, combine
Divide and conquer solves a problem of size n in three phases:
- Divide: split the input into two or more subproblems of the same type but smaller in size (usually two halves).
- Conquer: solve each subproblem recursively. When the subproblem is so small that the answer is immediate (one stop, one time slot), we are at the base case — the same concept we studied when covering recursion in 01-02.
- Combine: merge the partial solutions into the solution of the original problem.
flowchart TD
A["Problem of size n"] --> B["Divide"]
B --> C["Subproblem n/2"]
B --> D["Subproblem n/2"]
C --> E["Conquer (recursion)"]
D --> F["Conquer (recursion)"]
E --> G["Combine"]
F --> G
G --> H["Solution to the original problem"]
Notice that the recursion does almost all the work for us: our design effort concentrates on deciding how to divide and, above all, how to combine. The combine phase is where both the genius and the bugs usually hide.
When it applies (and when it doesn't)
Not every problem lets itself be chopped up. Divide and conquer works well when three conditions hold:
- The subproblems are of the same type as the original. Finding the maximum in half a list is still "finding the maximum in a list". If dividing changes the nature of the problem, the recursion doesn't fit.
- The subproblems are independent. Solving the left half needs nothing from the right half. This condition is crucial: if the subproblems overlap (they share work), divide and conquer repeats computations and becomes inefficient — that scenario is exactly the one dynamic programming will solve in 03-03.
- Combining is cheaper than solving from scratch. If merging the partial solutions costs as much as the whole problem, we have gained nothing.
| Condition | If it holds | If it doesn't |
|---|---|---|
| Subproblems of the same type | The recursion is natural | Look for another strategy |
| Independent subproblems | No repeated work | Dynamic programming (03-03) |
| Cheap combination | The total cost drops | Splitting buys nothing |
First RutaBus example: a line's rush hour
Let's start with a deliberately simple example to nail down the scheme. RutaBus records how many passengers board line L1 in each 15-minute slot. The planning department wants to know the rush hour: the maximum of that list of counts.
We could already solve this with an O(n) loop, as we did with nearest_stop in 01-01. Let's now solve it with divide and conquer to see the scheme in its purest form:
def max_passengers(counts, start, end):
"""Maximum of counts[start..end] (both inclusive) by divide and conquer."""
# BASE CASE: a single slot -> the maximum is itself
if start == end:
return counts[start]
# DIVIDE: split the range in half
middle = (start + end) // 2
# CONQUER: maximum of each half, recursively
max_left = max_passengers(counts, start, middle)
max_right = max_passengers(counts, middle + 1, end)
# COMBINE: the global maximum is the larger of the two partials
return max_left if max_left >= max_right else max_right
rush_hour = max_passengers(counts_l1, 0, len(counts_l1) - 1)
print(rush_hour) # 91Let's break down each piece:
- Base case (
start == end): a range of a single slot cannot be divided any further; its maximum is trivial. Without this case the recursion would never terminate — remember Knuth's finiteness property (01-01). - Divide: we compute
middleand get two ranges,[start..middle]and[middle+1..end]. Notice that we pass indices instead of taking slices (counts[:middle]): in 02-01 we saw that every slice copies data and costs O(k); with indices, dividing is O(1). - Conquer: two recursive calls, each over half of the slots.
- Combine: a single comparison, O(1).
The execution over the 8 slots forms a call tree:
flowchart TD
A["[0..7] → 91"] --> B["[0..3] → 78"]
A --> C["[4..7] → 91"]
B --> D["[0..1] → 45"]
B --> E["[2..3] → 78"]
C --> F["[4..5] → 91"]
C --> G["[6..7] → 64"]
D --> H["12"] & I["45"]
E --> J["78"] & K["33"]
F --> L["91"] & M["27"]
G --> N["64"] & O["50"]
An important confession: this algorithm makes exactly n − 1 comparisons, the same as the linear loop. Here divide and conquer gains nothing in time (and it also consumes recursion stack, as we analyzed in 02-02). We used it because it shows the scheme with total clarity. The real payoff appears when dividing lets us avoid work, as in the next example.
Second RutaBus example: the closest pair of stops in 1D
In 02-01 we wrote connectable_pairs, which compared every pair of stops: O(n²). A sibling problem: the infrastructure team wants to detect the two stops closest to each other along an avenue (if they are too close together, one is probably redundant). We simplify to 1D: each stop is represented by its kilometer mark along the avenue.
Brute force would compare the n(n−1)/2 pairs — the arithmetic sum we derived in 02-01 —: O(n²). Divide and conquer brings it down to O(n log n):
def min_distance(sorted_kms, start, end):
"""Minimum distance between two stops of sorted_kms[start..end].
Precondition: the list is sorted by kilometer."""
# BASE CASE: with fewer than two stops there is no possible pair
if end - start < 1:
return float("inf")
# DIVIDE
middle = (start + end) // 2
# CONQUER: best pair within each half
best_left = min_distance(sorted_kms, start, middle)
best_right = min_distance(sorted_kms, middle + 1, end)
# COMBINE: the winning pair may CROSS the boundary.
# Since the list is sorted, the only candidate crossing pair is
# (last of the left half, first of the right half).
crossing = sorted_kms[middle + 1] - sorted_kms[middle]
return min(best_left, best_right, crossing)
sorted_kms = sorted(kms) # [0.3, 0.9, 1.2, 2.8, 4.0, 5.1]
print(min_distance(sorted_kms, 0, len(sorted_kms) - 1))
# 0.3 -> between the stops at km 0.9 and 1.2Key points:
- The combine phase is no longer trivial: the best pair could have one stop in each half. Thanks to the prior sorting, it is enough to examine one boundary pair, not all the crossing ones.
- The base case returns
float("inf")("infinity"): a neutral value that never wins amin. It is a very common pattern for "no solution here". - To be honest: with the list already sorted, a simple pass over adjacent pairs would also solve this in O(n). We use the recursive version because (a) it illustrates a non-trivial combine step and (b) it is the direct gateway to the real problem in 2D (stops on a map), where the linear pass no longer exists and divide and conquer keeps exactly this structure.
Reasoning about cost: counting levels of division
How do you analyze an algorithm that calls itself twice? In 02-01 we counted recursive calls one by one; with divide and conquer there is a more convenient method: counting levels.
Each level of recursion divides the size by 2: n → n/2 → n/4 → … → 1. The question "how many times can I divide n by 2 until reaching 1?" has as its answer, precisely, log₂ n — the same intuition we associated with O(log n) in the hierarchy of 01-03.
The total cost is estimated like this:
total cost ≈ (number of levels) × (work per level)
| Divide + combine work per call | Work per level | Levels | Total cost |
|---|---|---|---|
O(1) (e.g.: max_passengers) |
the ~n leaves of the tree dominate | log₂ n | O(n) |
| O(n) spread across the level (e.g.: merging sorted halves) | O(n) at every level | log₂ n | O(n log n) |
Two readings of this table:
- In
max_passengers, each call combines in O(1); the tree has about2n − 1nodes in total, so the cost is O(n). That is why it didn't beat the loop: the leaves rule the work. - When combining costs O(n) per level, we have O(n) of work at each of the log₂ n levels: O(n log n), the star complexity of the good sorting algorithms.
This second pattern is formally written as the recurrence T(n) = 2·T(n/2) + O(n): "the cost for size n is that of two subproblems of size n/2 plus a linear combining effort". We will solve this recurrence with full rigor when we analyze merge sort in 04-03; for now, keep the levels method, which gives the correct answer in the usual cases.
Famous algorithms of the strategy
Divide and conquer is the birth certificate of several classics that we will study, now with complete implementations, in Module 4:
| Algorithm | How it divides | Cost | We'll see it in |
|---|---|---|---|
| Binary search | Discards one half at each step (just one subproblem!) | O(log n) | 04-01 |
| Merge sort | Sorts each half and merges them | O(n log n) | 04-03 |
| Quick sort | Partitions around a pivot | O(n log n) average | 04-04 |
| Karatsuba multiplication | Splits the numbers into halves of digits | ≈ O(n^1.585) | (mention only) |
We won't implement them here: in this module we care about the strategy; in Module 4, about the classics it spawned.
Common Mistakes and Tips
- Forgetting the base case or defining it wrong. An empty or single-element range must stop dead. Always test your function with
n = 0,n = 1andn = 2before trying large lists. - Dividing with slices instead of indices.
some_list[:middle]copies O(k) elements at every level (the hidden cost from 02-01) and blows up memory (02-02). Passstartandend. - Off-by-one errors at the boundary. If the halves were
[start..middle]and[middle..end](withmiddlerepeated), the recursion might not reduce the size and never terminate. Check that both halves are strictly smaller than the original range. - Ignoring the solutions that cross the boundary. In
min_distance, forgetting the boundary pair produces silently incorrect results. When designing the combine step, always ask yourself: "can the solution have one foot in each half?". - Applying the strategy out of inertia. If combining doesn't make anything cheaper (the maximum case), a simple loop is better: just as fast, more readable, and without spending recursion stack.
Exercises
Exercise 1
Write total_passengers(counts, start, end) that adds up the passengers of a range of slots using divide and conquer. Identify its base case and its three phases, and reason about its total cost by counting levels. Does it gain anything over sum(counts)?
Exercise 2
RutaBus wants the valley slot (minimum of passengers) and the rush hour (maximum) at the same time. Write min_and_max(counts, start, end) that returns the tuple (minimum, maximum) in a single divide-and-conquer pass.
Exercise 3
In min_distance, why is it essential that the list be sorted for the combine step to look at a single pair? Build a concrete unsorted list on which the algorithm, applied without sorting first, returns an incorrect result.
Solutions
Solution 1
def total_passengers(counts, start, end):
if start > end: # base case: empty range
return 0
if start == end: # base case: one slot
return counts[start]
middle = (start + end) // 2
left = total_passengers(counts, start, middle) # conquer
right = total_passengers(counts, middle + 1, end)
return left + right # combine: O(1)Combining costs O(1); as in max_passengers, the tree has ~2n nodes and the total cost is O(n). It gains nothing over sum (also O(n)) and on top of that consumes O(log n) of stack (02-02). A good scheme exercise; a bad idea in production.
Solution 2
def min_and_max(counts, start, end):
if start == end:
return (counts[start], counts[start])
middle = (start + end) // 2
min_l, max_l = min_and_max(counts, start, middle)
min_r, max_r = min_and_max(counts, middle + 1, end)
return (min(min_l, min_r), max(max_l, max_r))The beauty is that each call returns both answers at once and the combine step is still O(1); the total cost is O(n). (Fun fact: by refining the base case so that it processes pairs — compare the two elements once and decide which one competes for the minimum and which for the maximum —, this structure drops to ~1.5n comparisons versus the ~2n of computing minimum and maximum separately.)
Solution 3
The combine step only looks at the pair (kms[middle], kms[middle+1]) because, with the list sorted, any other crossing pair is further apart: the elements on the left are all ≤ kms[middle] and those on the right all ≥ kms[middle+1]. Without ordering, that guarantee disappears. Counterexample: [0.3, 5.1, 0.4, 9.0]. The halves give 4.8 (left: |5.1−0.3|) and 8.6 (right: |9.0−0.4|), and the boundary pair is |0.4−5.1| = 4.7. The algorithm would return 4.7, but the real answer is |0.4−0.3| = 0.1 — a crossing pair that the boundary doesn't see.
Conclusion
Divide and conquer has given us our first design mold: divide the problem into independent subproblems of the same type, conquer them recursively from a solid base case, and combine their answers — the phase where the real difficulty lives. We have learned to estimate its cost by counting levels (log₂ n divisions) and we have verified, with L1's rush hour, that the strategy only pays off when dividing saves work, as in the closest pair of stops (from O(n²) to O(n log n)). The most famous fruits of the mold — binary search, merge sort, quick sort — await us in Module 4. But first we must meet the rest of the family. Divide and conquer solves all the subproblems and then decides; the next strategy is far more impatient: at each step it takes the decision that looks best right now and never goes back. Sometimes that boldness produces optimal, blazing-fast algorithms; other times, silent disasters. They are the greedy algorithms, and learning to tell when they can be trusted is the goal of the next lesson.