COMP9123 — Week 11 Supplement
Mathematical Foundations
Setting up and solving recurrence relations for divide-and-conquer algorithms; recursion-tree analysis; the master theorem and its three cases; worked classifications for binary search, merge sort, quicksort, and Strassen.
Recurrences: the divide-and-conquer cost
A divide-and-conquer recurrence captures the cost of an algorithm in terms of its sub-call structure and combine work. The general shape is:
Standard form
\[ T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n), \quad a \ge 1,\ b > 1 \]
where \(a\) is the number of recursive sub-calls, \(b\) is the input-shrinking factor per call, and \(f(n)\) is the combined cost of the divide and combine steps.
The recursion tree has depth \(\log_b n\), and at level \(k\) it does \(a^k\,f(n/b^k)\) work. Summing the geometric series gives the total cost.
Master theorem
Compare the combine cost \(f(n)\) to the watershed function \(n^{\log_b a}\) and read off the answer.
Case 1 — \(f\) is dominated by the watershed
If \(f(n) \in O(n^{\log_b a - \varepsilon})\) for some \(\varepsilon > 0\): \[ T(n) \in \Theta\!\left(n^{\log_b a}\right) \]
Case 2 — \(f\) matches the watershed
If \(f(n) \in \Theta(n^{\log_b a})\): \[ T(n) \in \Theta\!\left(n^{\log_b a} \log n\right) \]
Case 3 — \(f\) dominates the watershed
If \(f(n) \in \Omega(n^{\log_b a + \varepsilon})\) for some \(\varepsilon > 0\) and \(a\,f(n/b) \le c\,f(n)\) for some \(c < 1\) (regularity): \[ T(n) \in \Theta(f(n)) \]
Worked Example 1: merge sort
\(T(n) = 2\,T(n/2) + n\). Identify \(a=2, b=2, f(n)=n\).
Watershed
\(n^{\log_b a} = n^{\log_2 2} = n^1 = n\).
Classification
\(f(n) = n = \Theta(n^{\log_b a})\), so we are in Case 2 and \(T(n) \in \Theta(n \log n)\).
The recursion-tree view confirms this: \(\log_2 n\) levels, each doing \(\Theta(n)\) work.
Worked Example 2: Strassen multiplication
Strassen's matrix multiplication has the recurrence \(T(n) = 7\,T(n/2) + n^2\).
Watershed
\(n^{\log_2 7} \approx n^{2.807}\), strictly above \(n^2\).
Classification
\(f(n) = n^2 \in O(n^{\log_2 7 - \varepsilon})\) for any sufficiently small \(\varepsilon\), so we are in Case 1: \(T(n) \in \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807})\).
This is the famous result that lets Strassen beat the naive \(\Theta(n^3)\) for matrix multiplication.
Common D&C recurrences cheat sheet
Binary search
\(T(n) = T(n/2) + 1\) → \(\Theta(\log n)\)
Merge / Quicksort
\(T(n) = 2T(n/2) + n\) → \(\Theta(n \log n)\)
Tree height
\(T(n) = 2T(n/2) + 1\) → \(\Theta(n)\)
Strassen
\(T(n) = 7T(n/2) + n^2\) → \(\Theta(n^{2.807})\)
For \(T(n) = 4T(n/2) + n\), the master theorem gives: