Editing Recurrence relation (section)

===Computer science===
Recurrence relations are also of fundamental importance in [[analysis of algorithms]].<ref>Cormen, T. et al, ''Introduction to Algorithms'', MIT Press, 2009</ref><ref>R. Sedgewick, F. Flajolet, ''An Introduction to the Analysis of Algorithms'', Addison-Wesley, 2013</ref> If an [[algorithm]] is designed so that it will break a problem into smaller subproblems ([[Divide and conquer algorithm|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 <math>n</math> 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 <math>n</math>.

A better algorithm is called [[Binary search algorithm|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

:<math>c_1=1</math>
:<math>c_n=1+c_{n/2}</math>

the [[time complexity]] of which will be <math>O(\log_2(n))</math>.