Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:cohene:home:chapter5 [2018/03/13 02:05] – [5.2: Further Recurrence Relations] cohene
+++ courses:cs211:winter2018:journals:cohene:home:chapter5 [2018/03/13 02:12] (current) – [5.3: Counting Inversions] cohene
@@ Line 23: / Line 23: @@
 ===== 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 "like". A problem that arises is when one must compare two rankings. To qualify this, we can count the number of inversions. An inversion occurs if indices i<j have the values ai>aj, and are not in order.
+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.