sorting and selection 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 doingintroduce 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 the case when is power of (we leave the problem of showing that our asymptotic characterization still holds in the general case as an exercise in this casewe can specify the definition of (nas if < ( ( / cn otherwise an expression such as the one above is called recurrence equationsince the function appears on both the leftand right-hand sides of the equal sign although such characterization is correct and accuratewhat we really desire is big-oh type of characterization of (nthat does not involve the function (nitself that iswe want closed-form characterization of (nwe can obtain closed-form solution by applying the definition of recurrence equationassuming is relatively large for exampleafter one more application of the equation abovewe can write new recurrence for (nas ( ( ( / (cn/ )cn ( / (cn/ cn ( / cn if we apply the equation againwe get ( ( / cn at this pointwe should see pattern emergingso that after applying this equation timeswe get ( ( / icn the issue that remainsthenis to determine when to stop this process to see when to stoprecall that we switch to the closed form (nb when < which will occur when in other wordsthis will occur when log making this substitutionthenyields ( log ( / log (log )cn nt( cn log nb cn log that iswe get an alternative justification of the fact that (nis ( log