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

Taught in

References