COMP9123 — Data Structures & Algorithms
Week 11: Divide and Conquer
Week 11 introduces a powerful design paradigm: split a problem into smaller versions of itself, solve them recursively, and combine. The lecture connects this idea to binary search, merge sort, and the family of recurrences that quantify divide-and-conquer running time, ending with the master theorem as a fast classification tool.
The divide-and-conquer recipe
Every divide-and-conquer algorithm in this lecture follows the same three-step skeleton. Recognising the skeleton makes new algorithms feel familiar and makes correctness arguments routine.
1. Divide
If the input is a base case (typically size 0 or 1), solve directly. Otherwise split it into several smaller parts.
2. Recur / Delegate
Solve each smaller part by recursively applying the same algorithm.
3. Conquer (Combine)
Stitch the sub-solutions together into a full solution. The combine step is where most algorithms do their interesting work.
Why this template?
Recursion gives a clean correctness story (induction on input size), and a clean cost story: total cost = divide + recurse + combine, captured by a recurrence.
Which step of divide and conquer is typically where the algorithm-specific insight lives?
Binary search: halving the work each call
Binary search is the smallest divide-and-conquer algorithm in the unit. It searches a sorted array \(A[0\ldots n-1]\) for a target by repeatedly comparing the target to the middle element and recursing on one half.
function binarySearch(A, left, right, target):
if left > right:
return -1 # base case: not found
mid = (left + right) // 2
if A[mid] == target:
return mid
if target < A[mid]:
return binarySearch(A, left, mid - 1, target)
else:
return binarySearch(A, mid + 1, right, target)Recurrence: \(T(n) = T(n/2) + O(1)\), giving \(T(n) \in O(\log n)\). Each recursive call halves the search interval and does constant work; \(\log_2 n\) levels of halving exhaust an array of size \(n\).
Binary search requires the input array to be:
Merge sort: divide, recurse, merge
Merge sort is the canonical divide-and-conquer sorting algorithm. Split the array in half, sort each half recursively, then merge the two sorted halves into one sorted output.
function mergeSort(A):
if length(A) <= 1:
return A # base case
mid = length(A) // 2
L = mergeSort(A[0 .. mid - 1])
R = mergeSort(A[mid .. end])
return merge(L, R) # linear-time merge of sorted listsMerge step
Walk two pointers through the two sorted halves; at each step take the smaller front element. Linear time \(O(n)\) and uses extra \(O(n)\) workspace.
Recurrence
\(T(n) = 2T(n/2) + O(n)\). The recursion tree has \(\log_2 n\) levels, each doing \(O(n)\) total work → \(O(n \log n)\) in every case.
Stable and not in-place. Merge sort preserves the order of equal keys (stable) but uses extra memory for the merged buffer. Compare to quicksort, which is in-place but unstable and worst-case \(O(n^2)\).
Recurrences: cost of a divide-and-conquer algorithm
Once you've written the algorithm, the running time is described by a recurrence \(T(n) = \text{divide}(n) + \text{recursive work} + \text{combine}(n)\). Solving the recurrence gives the asymptotic running time.
Binary search
\(T(n) = T(n/2) + O(1) \Rightarrow O(\log n)\). One subcall, constant combine.
Merge sort
\(T(n) = 2T(n/2) + O(n) \Rightarrow O(n \log n)\). Two subcalls of half size, linear combine.
Tree-traverse style
\(T(n) = 2T(n/2) + O(1) \Rightarrow O(n)\). Two subcalls of half size, constant combine (e.g. tree height computation).
Quicksort (best case)
\(T(n) = 2T(n/2) + O(n) \Rightarrow O(n \log n)\), with a worst case of \(O(n^2)\) when the pivot is bad.
A common technique is the recursion tree: draw the recurrence as a tree, sum the work per level, and multiply by the number of levels. This makes the asymptotic answer visible and gives intuition for the master theorem cases.
Master theorem: classify recurrences at a glance
The master theorem applies to recurrences of the form \(T(n) = a\,T(n/b) + f(n)\) with \(a \ge 1\), \(b > 1\). It compares the combine cost \(f(n)\) to the watershed function \(n^{\log_b a}\) and reads off the solution in one of three cases.
The three cases
Case 1. If \(f(n) \in O(n^{\log_b a - \varepsilon})\) for some \(\varepsilon > 0\), then \(T(n) \in \Theta(n^{\log_b a})\).
Case 2. If \(f(n) \in \Theta(n^{\log_b a})\), then \(T(n) \in \Theta(n^{\log_b a} \log n)\).
Case 3. If \(f(n) \in \Omega(n^{\log_b a + \varepsilon})\) and a regularity condition holds, then \(T(n) \in \Theta(f(n))\).
Merge sort → Case 2
\(a=2, b=2, f(n)=n\). Watershed \(n^{\log_2 2}=n\); since \(f(n)=\Theta(n)\) we are in Case 2 and \(T(n)\in\Theta(n\log n)\).
Binary search → Case 2 (degenerate)
\(a=1, b=2, f(n)=1\). Watershed \(n^0 = 1\); \(f = \Theta(1)\) so \(T(n)\in\Theta(\log n)\).
For the recurrence \(T(n) = 2T(n/2) + n\), the master theorem classification is:
Other classic divide-and-conquer algorithms
The paradigm scales well beyond binary search and merge sort. The lecture mentions several more (some only by name) to show the breadth of the technique.
Quicksort
Pick a pivot, partition, recurse on each side. Average-case \(O(n \log n)\), worst-case \(O(n^2)\) on bad pivots. Randomisation makes the average-case the practical case.
Closest pair of points
Sort by x, split, recurse, then merge with a strip check around the midline. \(O(n \log n)\) compared with the naive \(O(n^2)\).
Strassen matrix multiplication
Multiplies two \(n \times n\) matrices in \(O(n^{\log_2 7}) \approx O(n^{2.81})\) by exploiting clever recursive combinations. Beats the naive \(O(n^3)\).
Counting inversions
Modify merge sort to count out-of-order pairs during the merge step. Still \(O(n \log n)\).
Tutorial & problem lens: how to apply the paradigm
Knowing the master theorem is not enough — the skill is matching new problems to the divide-and-conquer template and writing the recurrence cleanly.
Setting up a recurrence
- Count how many recursive calls happen (\(a\)) and how the input size shrinks (\(b\)).
- Estimate the divide and combine work in terms of \(n\) to get \(f(n)\).
- Apply the master theorem or draw the recursion tree.
Common traps
- Forgetting the base case, which makes the recurrence undefined.
- Confusing \(\log_b\) with \(\log_2\) in the watershed term.
- Believing every recurrence fits one of the three master cases — some need substitution or recursion-tree analysis.
Worked exam question
Given \(T(n) = 3T(n/2) + n^2\), classify using the master theorem.
Watershed: \(n^{\log_2 3} \approx n^{1.585}\). Since \(f(n) = n^2 = \Omega(n^{1.585 + \varepsilon})\), we are in Case 3 and \(T(n) \in \Theta(n^2)\) (the combine work dominates).
Quiz Hub & spaced review
Practise the recurrence setup and master-theorem case selection — that is where most exam mistakes happen. Use the flashcards for the four classic D&C running times until you can recite them without effort.