COMP90038 · Algorithms And Complexity
Decrease-and-Conquer
The first design paradigm: solve a problem by reducing it to one smaller instance, solving that, and extending the answer — in contrast to divide-and-conquer, which splits into several sub-problems. The chapter sorts decrease-and-conquer into three flavours by how much you shrink each step. Decrease-by-a-constant (usually 1) gives insertion sort (Θ(n²) worst, Θ(n) on nearly-sorted data) and topological sort. Decrease-by-a-constant-factor halves the problem each step and so runs in Θ(log n) — binary search and fast (binary) exponentiation are the headline examples, and the halving is exactly why the cost is logarithmic. Decrease-by-a-variable-amount shrinks by a data-dependent quantity — quickselect (find the k-th smallest by partitioning around a pivot, Θ(n) expected) and Euclid's GCD. The unifying skill is spotting which single sub-instance to recurse on and how the answer extends, then reading the running time straight off the shrink rate.
What this chapter covers
- 01Decrease-by-constant: insertion sort (Θ(n²) / Θ(n) best)
- 02Decrease-by-constant-factor: binary search, fast exponentiation → Θ(log n)
- 03Decrease-by-variable-size: quickselect, Euclid's GCD
- 04Why halving the input gives a logarithmic cost
- 05Choosing the single smaller sub-instance and extending its answer
Worked example: binary exponentiation
- +1Write the exponent in binary. 13 = 1101₂, i.e. 8 + 4 + 1, so 313 = 38·34·31.
- +1Build the squaring chain. 3, 3²=9, 3⁴=81, 3⁸=6561 — each by squaring the previous (3 squarings).
- +1Multiply the chosen powers. 6561 × 81 × 3 = 1 594 323 (2 multiplications), so 5 multiplications total.
- +1Asymptotics. The number of squarings is ⌊log₂n⌋ and the number of selected powers is at most that, so the cost is Θ(log n) multiplications — versus n−1 for the naive method.
Key terms
- Decrease-and-conquer
- A design paradigm that reduces a problem to a single smaller instance, solves it (often recursively), and extends the solution. Distinct from divide-and-conquer, which splits into multiple sub-problems and combines them.
- Insertion sort
- Decrease-by-one sorting: assume the first k elements are sorted, then insert the (k+1)-th into place. Θ(n²) worst-case but Θ(n) on nearly-sorted input, and stable — the practical choice for small or almost-sorted arrays.
- Binary search
- Decrease-by-half search of a sorted array: compare the target with the middle element and recurse into one half. Θ(log n) comparisons; the canonical example of why halving yields logarithmic cost.
- Binary exponentiation
- Compute an in Θ(log n) multiplications by squaring repeatedly and multiplying in the powers picked out by the binary digits of n, instead of n−1 naive multiplications.
- Quickselect
- Find the k-th smallest element by partitioning around a pivot and recursing into only the side containing rank k. Θ(n) expected time (decrease-by-a-variable-amount), Θ(n²) worst-case with bad pivots.
Decrease-and-Conquer FAQ
How is decrease-and-conquer different from divide-and-conquer?
Decrease-and-conquer recurses on a single smaller instance (binary search throws away half and recurses once); divide-and-conquer splits into several sub-problems and combines their answers (mergesort splits into two halves and merges). The number of recursive calls per step is the giveaway.
Why does halving give a logarithmic running time?
Because you can only halve n down to 1 about log₂n times. Each step does O(1) work and reduces the problem by a constant factor, so the total number of steps — and hence the cost — is Θ(log n). This is the engine behind binary search and binary exponentiation.
Is quickselect related to quicksort?
Yes — both partition around a pivot, but quicksort recurses into both sides (sorting everything) while quickselect recurses into only the side holding the rank it wants. That single-sided recursion is what makes quickselect linear on average instead of n log n.
Exam move
Classify each algorithm by its shrink rate, because the rate is the running time: decrease-by-a-constant → usually Θ(n²) when nested or Θ(n) linearly; decrease-by-a-factor → Θ(log n); decrease-by-a-variable-amount → depends on the split (expected linear for quickselect). Practise binary exponentiation and binary search as margin traces, and be ready to argue why halving is logarithmic in a Q2 justification. Spotting that you only need one smaller sub-instance is the design cue that separates this paradigm from divide-and-conquer.
