Divide and Conquer
Split the input, solve the pieces with the same function, and spend what is left of the budget combining them.
Divide and conquer cuts an input into a few smaller instances of the same problem, recurses on each, then combines the results. The cut and the combine are the design; the recursion itself is mechanical. Merge sort splits in half for free and pays n to merge, quick sort pays n to partition and gets the combine for free, and between them that is the whole idea.
The running time is read off the recursion tree. a subproblems of size n / b with f(n) work at each node gives T(n) = a T(n / b) + f(n), and which of the leaves, the root or every level dominates is exactly what the master theorem decides. It is also why merge sort is n log n while binary search, which throws one half away instead of solving it, is log n.
Speed comes from shrinking a or f(n). Karatsuba multiplies two n-digit numbers with three half-size products instead of the obvious four, which turns n^2 into about n^1.585; Strassen does the same for matrices, seven block products instead of eight. Both buy fewer multiplications with more additions, so both only pay off above a size threshold.
After this you can
- Write an algorithm as split, recurse, combine, and price each of the three parts
- Turn that shape into a recurrence and read the running time off the recursion tree
- Tell apart a split that discards one half and a split that solves both
- Say why three half-size products beat four, and when the extra additions eat the gain
Range 0-7 has 8 elements. Split at 3: recurse on 0-3, then on 4-7, and combine afterwards. Depth 0.
In this order
- Divide and ConquerSplit the input, solve the parts recursively, combine the results.
- Binary Search (recursive view)Each call probes the middle and recurses into the half that can still hold the target; depth O(log n).
- Merge SortMerge two sorted runs by always taking the smaller front value.
- Recurrence RelationsT(n) = a T(n / b) + f(n), the cost equation of a recursive algorithm, read off its recursion tree.
- Karatsuba MultiplicationMultiply n-digit numbers with three half-size products instead of four.
- Closest Pair (divide and conquer)Split points by x, recurse, then check a strip around the split line.
- Strassen Matrix MultiplicationSeven block products instead of eight.
Where people go wrong
A combine that costs more than the split saves
Recursion buys nothing if the pieces are expensive to put back together: T(n) = 2 T(n / 2) + n^2 is still n^2, because the top level alone does as much work as everything beneath it. That is the master theorem's third case.
Recursing all the way to one element
At eight elements the call overhead and the copying cost more than an insertion sort over the same eight. Real implementations stop recursing below a threshold of roughly 16 and finish with the simple algorithm.
Pieces that are not independent
Naive Fibonacci splits into f(n-1) and f(n-2), which share almost all of their work, so the recursion recomputes the same values exponentially often. Overlapping pieces are the signal to cache rather than to split further.
Or a different category
Dynamic Programming
The pieces overlap, so the same subproblem is asked about many times and the answers are worth storing.
Sorting
You want the split-and-combine algorithms themselves, with their stability and memory trade-offs.