12.4. Basic Ranking and Inversions

Try these first

1. 1.

   Define what an inversion is in rankings.

   Hint

   Think about the opposite ranking of two items.

2. 2.

   What is the time complexity of counting inversions using a brute-force approach?

   Hint

   Consider checking each pair of items.

3. 3.

   What is the definition of an inversion?

   • A count of similar preferences
   • A count of opposite ranking pairs
   • Total number of items

   Hint

   Think of pairs that are ranked differently.

4. 4.

   True or False: A merge sort with inversion counting can achieve time complexity of O(n log n).

   • True
   • False

   Hint

   Consider the efficiency of merge sort.

5. 5.

   Given the rankings [4, 3, 2, 1], calculate the total number of inversions and explain the reasoning.

   Hint

   Think about how each element can be paired with elements to its right.

6. 6.

   Design a function that counts inversions in an array. Demonstrate with an example.

   Hint

   How does merging relate to counting inversions?