Recurrence
This chapter introduces recursive algorithms and how they can be analyzed.
The word recurrence literally means the fact of occurring again.
Merge Sort
Merge sort is a typical textbook example of a recursive algorithm. The idea is very simple: We divide the array into two equal parts, sort them recursively, and then combine the two sorted arrays. The base case for recursion occurs when the size of the array reaches a single element. An array consisting of a single element is already sorted.
We'll determine the time complexity of merge sort by unrolling the recursive calls made by the algorithm to itself, and examining the cost at each level of recursion. The total cost is the sum of individual costs at each level.
The running time for a recursive solution is expressed as a recurrence equation (an equation or inequality that describes a function in terms of its own value on smaller inputs). The running time for a recursive algorithm is the solution to the recurrence equation. The recurrence equation for recursive algorithms usually takes on the following form:Running Time = Cost to divide into n subproblems + n * Cost to solve each of the n problems + Cost to merge all n problems
In the case of merge sort, we divide the given array into two arrays of equal size, i.e. we divide the original problem into sub-problems to be solved recursively.
Following is the recurrence equation for merge sort. Running Time = Cost to divide into 2 unsorted arrays + 2 * Cost to sort half the original array + Cost to merge 2 sorted arrays
...