Divide and Conquer
Split the input, solve the pieces with the same function, and spend what is left of the budget combining them.
Recursion Trees: Divide and conquer over a range
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
In this order
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.