structural:reformatting, structural:expansion, quality:correction
Computer science

Recurrence relations are also of fundamental importance in analysis of algorithms. If an algorithm is designed so that it will break a problem into smaller subproblems (divide and conquer), its running time is described by a recurrence relation.

A simple example is the time an algorithm takes to find an element in an ordered vector with n {\displaystyle n} elements, in the worst case.

A naive algorithm will search from left to right, one element at a time. The worst possible scenario is when the required element is the last, so the number of comparisons is n {\displaystyle n}.

A better algorithm is called binary search. However, it requires a sorted vector. It will first check if the element is at the middle of the vector. If not, then it will check if the middle element is greater or lesser than the sought element. At this point, half of the vector can be discarded, and the algorithm can be run again on the other half. The number of comparisons will be given by

the time complexity of which will be O (log 2 (n)) {\displaystyle O(\log _{2}(n))}.