Algorithm design: divide and conquer and greedy
Divide and Conquer and Greedy: definitions, design templates, Master Theorem, proofs (exchange argument), and worked Python programs (Merge Sort, Activity Selection) with exam-focused notes.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Engineers use divide and conquer when a problem can be split into smaller independent subproblems that look like the original, such as sorting large datasets or processing images. Greedy algorithms are used when local choices that look best right now lead to a globally optimal solution, such as scheduling, compression, and routing under constraints. Knowing when and why each approach works helps you design fast, simple, and correct software.
Key ideas
Divide and Conquer (D&C): Definition: Divide and conquer is a design paradigm that solves a problem of size n by (i) dividing it into a subproblems (a ≥ 1) of size about n/b each (b > 1), (ii) conquering by solving subproblems recursively, and (iii) combining their solutions (and doing any dividing) in f(n) time to get the full solution. Assumes subproblems are the same type as the original and independent enough to be solved separately.
- Structure: Divide → Recurse → Combine. Typical recurrence: T(n) = a·T(n/b) + f(n), with T(1) = Θ(1), where a is number of subproblems, b is factor of size reduction, and f(n) is cost outside recursion (divide + combine).
- Examples: Merge sort, quick sort (in separate topic), binary search (separate topic), fast exponentiation, closest pair of points.
Greedy algorithm: Definition: A greedy algorithm builds a solution step by step by repeatedly making a locally optimal choice (based on a fixed rule) with no reconsideration of previous choices. Assumes two properties to be correct: optimal substructure and greedy-choice property.
- Optimal substructure: An optimization problem has optimal substructure if an optimal solution to the whole problem contains within it optimal solutions to subproblems.
- Greedy-choice property: A problem has the greedy-choice property if there exists an optimal solution that can be obtained by making a locally optimal choice first, and then solving the remaining subproblem optimally (often provable by an exchange argument).
- Examples: Activity selection by earliest finish time, Dijkstra’s shortest path on non-negative weights (separate topic), Huffman coding (separate topic), Kruskal’s and Prim’s MST (separate topic), coin change for canonical coin systems.
Exact statement (standard form) of the Master Theorem for recurrence solving (for D&C): Let T(n) satisfy T(n) = a·T(n/b) + f(n) for constants a ≥ 1, b > 1, and for sufficiently large n, with T(n) positive and defined on integer n that are powers of b (extensions to all n by smoothness/monotonicity). Let n^{log_b a} be the critical function.
- Case 1 (small f): If f(n) = O(n^{log_b a − ε}) for some ε > 0, then T(n) = Θ(n^{log_b a}).
- Case 2 (balanced): If f(n) = Θ(n^{log_b a} · (log n)^k) for some k ≥ 0, then T(n) = Θ(n^{log_b a} · (log n)^{k+1}).
- Case 3 (large f + regularity): If f(n) = Ω(n^{log_b a + ε}) for some ε > 0 and there exists a constant 0 < c < 1 and n0 such that a·f(n/b) ≤ c·f(n) for all n ≥ n0 (regularity condition), then T(n) = Θ(f(n)). Assumptions: a, b constants; f(n) asymptotically positive; and the regularity condition is required in Case 3 to prevent pathological oscillations.
Standard derivation method for D&C recurrences (recursion-tree or expansion):
- Write T(n) = a·T(n/b) + f(n).
- Expand one level: = a[a·T(n/b^2) + f(n/b)] + f(n) = a^2·T(n/b^2) + a·f(n/b) + f(n).
- After i levels: T(n) = a^i·T(n/b^i) + Σ_{j=0}^{i−1} a^j·f(n/b^j).
- Stop when n/b^i = 1 ⇒ i = log_b n. So T(n) = a^{log_b n}·T(1) + Σ_{j=0}^{log_b n−1} a^j·f(n/b^j).
- Use algebra and bounds on the sum to match Master Theorem cases.
Correctness proof technique for greedy: Exchange argument. Statement: To prove a greedy rule is correct, show that, for any optimal solution O, if O differs from the greedy choice at the earliest position, you can exchange choices to make O at least as good while making it agree with greedy at that position. Repeating exchanges transforms O into the greedy solution without reducing quality, proving optimality. Assumes feasible exchanges exist and cost/benefit is preserved or improved by the swap.
Example specific: Activity Selection Problem. Problem: Given n activities with start times s_i and finish times f_i (non-overlapping if one finishes at or before another starts), select a maximum-size subset of mutually compatible activities. Greedy rule: Select the activity with the earliest finishing time among those that start after the last selected activity finishes. Repeat. Exchange proof sketch: Let A_g be greedy solution, O be any optimal solution. Compare first chosen activities; if O’s first activity finishes later than A_g’s, swapping A_g’s first activity into O keeps feasibility and does not reduce the number of activities. Repeat to align O with A_g. Diagram to draw (exam): Draw a horizontal time axis. Draw activities as intervals [s_i, f_i] as line segments. Mark greedy picks with solid segments and non-picked with dashed. Label earliest-finish choice and the swap step, showing feasibility preserved.
Example specific: Merge Sort (D&C). Idea: Divide array into two halves, recursively sort each half, and merge two sorted halves in linear time. Recurrence: T(n) = 2·T(n/2) + Θ(n) ⇒ by Master Theorem Case 2 (k = 0), T(n) = Θ(n log n). Diagram to draw (exam): A binary recursion tree of height log₂ n. Each level shows subarrays and their sizes. Annotate per-level work as n (for merging). Sum across levels to get n log₂ n total work.
When to choose which paradigm:
- Use divide and conquer when subproblems are similar and independent, and combining is efficient (e.g., sorting, searching, numeric algorithms).
- Use greedy when you can prove greedy-choice property and optimal substructure (e.g., scheduling, MST, specific shortest paths). If in doubt, try dynamic programming (separate topic) and see if a monotone structure suggests a greedy rule.
Formulas
n^{log_b a}— Critical function in Master Theorem; n is input size, a and b as above; compares growth of f(n) to subproblem work. Unitless growth rate.Θ(n log n)— Asymptotic running time for merge sort; n: number of elements; log is base 2 unless stated; unitless growth rate.- Python syntax template (D&C recursion):
def solve(x): if base_case(x): return trivial_answer(x) left, right = divide(x) sol_left = solve(left) sol_right = solve(right) return combine(sol_left, sol_right)— Use for problems where subproblems are independent and combination is defined. - Python syntax template (Greedy loop):
def greedy(items): items.sort(key=rule) sol = empty() for it in items: if feasible(sol, it): sol.add(it) return sol— Use when greedy-choice property holds; choose rule that gives locally best next step.
Worked examples
- Program: Merge Sort using Divide and Conquer Complete Python code:
from typing import List
def merge(left: List[int], right: List[int]) -> List[int]:
i = j = 0
out = []
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
out.extend(left[i:])
out.extend(right[j:])
return out
def merge_sort(arr: List[int]) -> List[int]:
n = len(arr)
if n <= 1:
return arr[:]
mid = n // 2
left_sorted = merge_sort(arr[:mid])
right_sorted = merge_sort(arr[mid:])
return merge(left_sorted, right_sorted)
if __name__ == '__main__':
# Sample input
data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data))
Sample input (embedded in program): [38, 27, 43, 3, 9, 82, 10] Exact output: [3, 9, 10, 27, 38, 43, 82] Explanation summary: Recurrence T(n) = 2·T(n/2) + Θ(n) ⇒ Θ(n log n). Stable, comparison-based, out-of-place in this implementation (extra space Θ(n)).
- Program: Activity Selection using Greedy (earliest finish time) Complete Python code:
from typing import List, Tuple
def select_activities(activities: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
# activities: list of (start, finish)
acts = sorted(activities, key=lambda x: x[1]) # sort by finish time
result: List[Tuple[int, int]] = []
current_end = float('-inf') # effectively -∞; works for any numeric times
for (s, f) in acts:
if s >= current_end:
result.append((s, f))
current_end = f
return result
if __name__ == '__main__':
# Sample input
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
picked = select_activities(activities)
print(picked)
Sample input (embedded in program): [(1, 4), (3, 5), (0, 6), (5, 7), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)] Exact output: [(1, 4), (5, 7), (8, 11), (12, 14)] Explanation summary: Sorting by finish time ensures earliest finishing activity is always chosen if compatible. Time complexity: sort O(n log n), scan O(n), total O(n log n). Correctness via exchange argument (see below).
- Theory model answer: Prove the greedy rule for Activity Selection is optimal (exchange argument)
- Statement to prove: The algorithm that repeatedly picks the available activity with the earliest finish time produces a maximum-size set of mutually compatible activities.
- Proof (exchange argument): Let G = ⟨g1, g2, …, gk⟩ be the sequence selected by the greedy algorithm in order of finishing times. Let O = ⟨o1, o2, …, om⟩ be any optimal solution with maximum number m of compatible activities, also ordered by finishing times. We show by induction on position t that there exists an optimal solution whose first t activities equal g1, …, gt, and whose size is m. Base t = 1: Greedy picks g1 with the earliest finish among all activities. If o1 = g1, done. If not, f(g1) ≤ f(o1). Replace o1 by g1 in O. Because g1 finishes no later than o1, all subsequent activities in O that were compatible with o1 remain compatible with g1. The set size stays m and remains feasible. Inductive step: Assume there is an optimal solution whose first t positions equal g1…gt. Consider position t+1. Greedy picks gt+1 as the earliest-finishing activity compatible with gt. If the optimal solution’s (t+1)-th activity equals gt+1, done. Otherwise, swap its (t+1)-th activity with gt+1 as in the base case; feasibility is preserved and the total count stays m. By repeated swapping, we transform O into a solution beginning with G without reducing its size; hence k = m and G is optimal. Therefore the greedy rule is correct. Diagram to draw (exam): Draw time axis; plot O’s first activity o1 above axis, g1 below; show f(g1) ≤ f(o1) and that replacing o1 by g1 opens at least as much “free space” for later activities. Repeat conceptually for further positions.
Common mistakes
- Misapplying the Master Theorem when parameters are not constants (e.g., b depends on n) or when the regularity condition for Case 3 is not checked.
- Forgetting base cases in recursive code (n = 0 or n = 1) leading to infinite recursion or wrong results.
- Confusing optimal substructure (needed by both greedy and dynamic programming) with the greedy-choice property (needed only by greedy).
- For merge sort, saying the space is O(1) for a standard merging implementation; typical array-based merge uses O(n) auxiliary space unless using linked lists or in-place variants.
- In activity selection, sorting by start time instead of finish time; that rule is not optimal.
- Mixing big-O with Θ in final complexity statements without justification; use Θ when you know tight bounds (e.g., merge sort time is Θ(n log n)).
For your exam
- Derivations: Solve T(n) = 2T(n/2) + n and T(n) = 3T(n/3) + n; derive using recursion tree and/or Master Theorem, showing each step and identifying the case. Full marks: correct identification of a, b, f(n); show n^{log_b a}; verify regularity if claiming Case 3.
- Programs: Implement merge sort; implement activity selection; outline D&C template or greedy template in pseudocode/Python. Full marks: correct I/O, correct sorting/selection rule, handle edge cases (empty list), and state time complexity.
- Proof-type: Prove correctness of earliest-finish-time rule for activity selection; give an exchange argument; optionally mention counterexamples for wrong rules. Full marks: clear structure (statement, construction of exchange, preservation of feasibility, no loss in optimality).
- Diagrams: Recursion tree for merge sort with per-level work n and height log₂ n; timeline intervals for activity selection showing swaps. Full marks: correct labels: n at each level, total cost sum; s_i and f_i for intervals; greedy picks highlighted.
Quick check
- State the Master Theorem and identify the case to solve T(n) = 2T(n/2) + n.
- What two properties must hold for a greedy algorithm to be guaranteed optimal? Give one example problem where they hold.
- In merge sort, what is the time complexity and what is the typical extra space used by a standard array-based implementation?
Answers: 1) Master Theorem as stated; here a = 2, b = 2, f(n) = n = Θ(n^{log_2 2}·(log n)^0) ⇒ Case 2 ⇒ T(n) = Θ(n log n). 2) Optimal substructure and greedy-choice property; example: activity selection with earliest-finish-time rule. 3) Time Θ(n log n); extra space Θ(n) for auxiliary arrays during merging.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?