merge-sort and recurrence equations there is another way to justify that the running time of the merge-sort algorithm is ( log (proposition namelywe can deal more directly with the recursive nature of the merge-sort algorithm in this sectionwe present such an analysis of the running time of merge-sortand in so doing introduce the mathematical concept of recurrence equation (also known as recurrence relationlet the function (ndenote the worst-case running time of merge-sort on an input sequence of size since merge-sort is recursivewe can characterize function (nby means of an equation where the function (nis recursively expressed in terms of itself in order to simplify our characterization of ( )let us restrict our attention to