5.1 - A First Recurrence: The Mergesort Algorithm

Recall: Mergesort sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion and then combinging the results of these recursive calls using the linear time alg. for merging sorted lists that we saw in Chapter 2.

Consider any algorithm that fits into the above rough problems and let T(n) denote its worst-case running time on input instances of size n. Supposing that n is even, the algorithm spends O(n) time to divide the input into two pieces of size n/2 each; it then spends time T(n/2) to solve each one and finally it spends O(n??) time to combine the solutions from the two recursive calls, and thus, the running time T(n) satisfies the following recurrence relation: For some constant c, T(n) ≤ 2T(n/2) + cn, when n > 2, and T(2) ≤ c. Approaches to solving recurrences Two basic ways: Unroll the recursion In regards to Figure 5.1 on p212 * Analyzing the first few levels: At the first level of recursion, we have a single problem of size n, which takes at most cn plus the time spent in all subsequent recursive calls. At the next level, we have two problems each of size n/2, that take at most c/2, for a total of at most c again plust the time in subsequent recursive calsls. At the third level, we have four problems each of size n/4, each taking at most cn/4, for a total of most cn. * Identifying a pattern: What's going on in general as recursion expands? * Summing over all levels of recurrence:sums all runtimes Any function T(.) satisfying (5.1) is bounded by O(n log n), when n>1. Substituting a Solution into the Mergesort Recurrence If we have a guess for the running time that we want to verify, we can do so by plugging it into the recurrence. An approach using Partial Substitution Weaker kind of substitution - guess overall form of solution without pinning down exact values at the outset. This section was a 6.5; I don't think I understand this yet. ====== 5.3 - Counting Inversions ======