Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:cohene:home:chapter5 [2018/03/12 23:40] – [5.1: A First Recurrence: The Mergesort Algorithm] cohene | courses:cs211:winter2018:journals:cohene:home:chapter5 [2018/03/13 02:12] (current) – [5.3: Counting Inversions] cohene | ||
|---|---|---|---|
| Line 16: | Line 16: | ||
| ===== 5.2: Further Recurrence Relations===== | ===== 5.2: Further Recurrence Relations===== | ||
| + | Like Mergesort, there is a general class of algorithms that have recursive calls on q subproblems of size n/2 and then combine results in O(n) time. | ||
| + | For the case of q>2, however, we unroll this following the previous style. First, we analyze the first few levels, and then identify a pattern. Finally, we apply a partial substitution. | ||
| + | When q=1, the outcome is entirely different, however, we still solve the problem the same way. We can sum this up as any function with q=1 is bounded by O(n). | ||
| ===== 5.3: Counting Inversions===== | ===== 5.3: Counting Inversions===== | ||
| + | This problem occurs when trying to analyze rankings. Websites such as Facebook use this method when trying to find things one might " | ||
| + | We can count the inversions in O(n log n) time. First, we divide the list into two pieces, and count the number of inversions in each half separately. Then, we count the number of inversions between the two halves. This routine is known as Merge-and-Count. When comparing the two lists, we take the smaller one and append it to a new list. | ||
