recurrence relation
An equation that defines an algorithm's cost on input size n in terms of its cost on smaller inputs, such as T(n) = 2T(n/2) + n.
In more detail
For merge sort, 2T(n/2) is the cost of sorting two halves and n the cost of merging. Picturing it as a recursion tree, each of the log n levels does n work in total, giving O(n log n). T(n) = T(n/2) + 1, one half plus constant work, gives binary search's O(log n).
Related terms
- divide and conquer — A problem-solving technique that splits a problem into independent smaller pieces, solves each recursively, and combines their answers.
- master theorem — A ready-made rule that solves recurrences of the form T(n) = aT(n/b) + f(n) by comparing f(n) with n raised to log base b of a.
- recursion tree — A picture of a recursive algorithm's calls as a tree, with the work done at each call written beside it, used to total the cost.
Taught in
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers