Divide and conquer
An algorithm design paradigm dividing problems into smaller subproblems of same type, solving recursively, and combining solutions. Divide-and-conquer enables efficient algorithms for sorting, searching, and matrix operations. Correctness depends on subproblem independence and solution combinability. Time complexity analysis uses recurrence relations.
Formula
T(n) = aT(n/b) + O(n^d)
Real World
Merge sort, used internally by Python's Timsort and Java's Arrays.sort, divides an array in half, recursively sorts each half, then merges — this divide-and-conquer approach guarantees O(n log n) even on worst-case input.
Exam Focus
Name all three stages — divide, conquer, combine — and link each to a concrete step in your chosen example.
How well did you know this?