recurrence relation
A recurrence relation describes the cost of solving a problem of size n in terms of the cost of solving smaller versions of the same problem. It is the natural language of recursion: if an algorithm works by breaking its input into pieces and calling itself on those pieces, then its running time obeys an equation that refers back to itself. We write the total work as T(n), where T stands for 'time' and n is the input size.
The classic example is merge sort. To sort n items it splits them into two halves, sorts each half, then merges the two sorted halves back together. Sorting each half is the same problem at half the size, so each costs T(n/2); the merge step walks through all n items once, costing O(n). Putting that together gives T(n) = 2T(n/2) + O(n). The recurrence does not yet tell you the answer — it tells you the shape of the work, and you still have to 'solve' it to get a plain bound like O(n log n).
Two things make a recurrence complete. First, a base case: a small enough input that you handle directly without recursing, such as T(1) = O(1) for a single element. Without a base case the relation would unwind forever. Second, a method to solve it — by drawing a recursion tree and summing the work at each level, by guessing a bound and proving it by induction, or by quoting a ready-made formula like the master theorem. The recurrence is the question; the closed-form Big-O is the answer.
// merge sort: cost of size n in terms of size n/2
long long T(long long n) {
if (n <= 1) return 1; // base case: T(1) = O(1)
return 2 * T(n / 2) + n; // two halves + an O(n) merge
}
// the equation T(n) = 2T(n/2) + n is the recurrence;
// its closed-form solution is O(n log n).T(n) = 2T(n/2) + O(n) with base case T(1) = O(1) solves to O(n log n).
A recurrence describes the cost; solving it (recursion tree, induction, or the master theorem) turns it into a plain Big-O bound.