Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:nasona:chapter5 [2018/03/11 22:07] – [5.1 The Mergesort Algorithm] nasona | courses:cs211:winter2018:journals:nasona:chapter5 [2018/03/11 22:21] (current) – [5.3 Counting Inversions] nasona | ||
|---|---|---|---|
| Line 51: | Line 51: | ||
| ==Summary== | ==Summary== | ||
| + | Now, we need to consider divide and conquer algorithms that create recursive calls on q subproblems of size n/2 and comibine the results in linear time. We already handled when q=2 with mergesort. When q > 2, the recurrence relation is T(n) <= qT(n/2) + cn when n > 2 and T(2) <=c. By unrolling the recursion, we come to the conclusion that the runtime of the algorithm is O(n^(log2q)). When q = 1, by unrolling the recurrence, we get that T(n) <= 2cn = O(n). A related recurrence of T(n) < | ||
| ==The Case of q>2 Subproblems== | ==The Case of q>2 Subproblems== | ||
| Line 112: | Line 113: | ||
| ==Summary== | ==Summary== | ||
| + | We want to be able to tell how far away a list is from being in order. In order to do this, we just have to count the number of inversions. The brute force solution to the algorithm runs in O(n^2) time, but we can do better than that. We will divide the list in half, count the number of inversions in each piece, and make the algorithm recursively sort the two halves. Once we get the two sorted halves, we want to combine them into a single sorted list while counting the number of inversions as we go. The Merge-and-Count routine takes O(n) time and the Sort-and-Count algorithm takes a total O(nlogn) time. | ||
| ==The Problem== | ==The Problem== | ||
