A binomial-tree pricer that halves the time step and reprices, a covariance-matrix routine that splits a large matrix multiplication into four sub-multiplications, and mergesort itself all share one shape: solve a problem by splitting it into smaller instances of the same problem, solving those recursively, then combining the sub-answers. This note formalises that shape as the divide-and-conquer design pattern, shows how it produces a recurrence for the running time, and introduces the master theorem — the standard tool for reading off a recurrence's asymptotic solution in asymptotic notation without re-deriving a recursion tree from scratch each time. The maximum-subarray problem is the running worked example; the theorem's proof is carried in a sibling derivation note so the statement and its use stay at reading pace here.
Learning objectives. By the end of this note you should be able to:
- recognise a divide-and-conquer algorithm and write down the recurrence it generates;
- solve simple recurrences with the substitution method and the recursion-tree method;
- state the master theorem's three cases and apply the theorem to a given recurrence, including recognising when none of the three cases applies;
- solve the maximum-subarray problem via divide-and-conquer and derive its cost from the recurrence.
In this lesson
- The divide-and-conquer pattern
- Solving recurrences
- The master theorem
- Divide-and-conquer beyond sorting: the maximum-subarray problem
Before you start
The full lesson, with worked examples and exercise solutions, is for members.
Read the full lessonNew to SelfMadeQuant.com? See membership options or explore the curriculum.