asymptotic characterization still holds in the general case as an exercise in this casewe can specify the definition of (nas 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 times we get ( it( / iicn 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 ( lognt( / logn(logn)cn nt( cnlogn nb cnlogn that iswe get an alternative justification of the fact that (nis (nlogn quick-sort the next sorting algorithm we discuss is called quick-sort like merge-sortthis algorithm is also based on the divide-and-conquer paradigmbut it uses this technique in somewhat opposite manneras all the hard work is done before the recursive calls high-level description of quick-sort