COMP90038 · Algorithms And Complexity
Divide-and-Conquer and the Master Theorem
The paradigm that splits a problem into several sub-problems of (usually) equal size, solves them recursively, and combines the results. Mergesort (split in half, sort each, merge in Θ(n)) gives a guaranteed Θ(n log n); quicksort (partition around a pivot, recurse on each side) is Θ(n log n) expected but Θ(n²) on bad pivots, and the chapter is careful about that distinction. The centrepiece is the Master Theorem for recurrences of the form T(n) = aT(n/b) + Θ(nd): compute the watershed exponent logba and compare it with d — leaves dominate (Case 1, Θ(nlogba)), a tie (Case 2, an extra log factor, Θ(nd log n)), or the root dominates (Case 3, Θ(nd)). The exam tests the four-parameter ritual directly — write a, b, d, name the case, justify — and pairs it with binary-tree traversal and reconstructing a tree from two traversals then reading off the third. The trap: the Master Theorem only applies to equal-sized sub-problems; an uneven split needs a recurrence tree.
What this chapter covers
- 01Mergesort — the guaranteed Θ(n log n) merge
- 02Quicksort — Θ(n log n) expected, Θ(n²) worst-case pivots
- 03The Master Theorem and the watershed exponent logba vs d
- 04The four-parameter ritual: write a, b, d → name the case → justify
- 05Binary-tree traversals; reconstruct from two, read off the third
Worked example: name the Master-Theorem case
- +2(i) a=7, b=2, d=2: log₂7 ≈ 2.807 > 2 → Case 1, T(n) = Θ(nlog₂7) ≈ Θ(n2.81).
- +1(ii) a=2, b=2, d=1: log₂2 = 1 = d → Case 2, T(n) = Θ(n log n).
- +2(iii) a=2, b=2, d=2: log₂2 = 1 < 2 = d → Case 3, T(n) = Θ(n²) (the combine cost dominates).
Key terms
- Divide-and-conquer
- Split a problem into several smaller sub-problems (usually equal-sized), solve each recursively, and combine their solutions. Mergesort and quicksort are the archetypes; the running time follows from a recurrence solved by the Master Theorem.
- Mergesort
- Divide-and-conquer sort: split in half, sort each half recursively, and merge the two sorted halves in Θ(n). Guaranteed Θ(n log n) in all cases and stable, at the cost of Θ(n) extra space for the merge.
- Quicksort
- Partition around a pivot so smaller elements go left and larger right, then recurse on each side. Θ(n log n) expected with good pivots, but Θ(n²) worst-case (sorted input with a naive pivot); in-place and fast in practice.
- Master Theorem
- Solves T(n) = aT(n/b) + Θ(nd) by comparing logba with d: Case 1 (logba > d) gives Θ(nlogba); Case 2 (equal) gives Θ(nd log n); Case 3 (logba < d) gives Θ(nd). Requires equal-sized sub-problems.
- Recurrence tree
- A method for solving recurrences by expanding the recursion into a tree and summing the work per level — the fallback when the Master Theorem does not apply (uneven splits, non-polynomial combine cost).
Divide-and-Conquer and the Master Theorem FAQ
How do I apply the Master Theorem step by step?
Write the recurrence as T(n) = aT(n/b) + Θ(nd), identify a, b and d, compute logba, and compare it with d. logba > d → Case 1 (Θ(nlogba)); equal → Case 2 (Θ(nd log n)); less → Case 3 (Θ(nd)). Always show a, b, d — the marks are in the comparison, not the final symbol.
When does the Master Theorem NOT apply?
When the sub-problems are not equal-sized (e.g. T(n) = T(n/3) + T(2n/3) + n), when a or b is not constant, or when the combine cost is not of the form Θ(nd). In those cases use a recurrence tree or the substitution method instead.
How do I reconstruct a binary tree from its traversals?
Pre-order (or post-order) gives the root; in-order then splits the remaining nodes into the left and right subtrees around that root. Recurse on each part. With pre-order + in-order, or post-order + in-order, the tree is unique — then you can read off the missing traversal.
Exam move
Make the four-parameter ritual a reflex, because Q1 and Q3–Q10 both lean on it: write a, b, d, compute logba, compare with d, name the case, and quote the Θ — never skip straight to the answer, because the comparison carries the marks. Keep mergesort (Θ(n log n) guaranteed) and quicksort (expected vs worst-case) crisply distinguished. Practise reconstructing a small binary tree from two traversals and reading off the third, a recurring Q1 move. And remember the trap: unequal splits fall outside the Master Theorem and need a recurrence tree.
