12.6. Brute Force Approach to Count Inversions

Try these first

1. 1.

   Define what an inversion is.

   Hint

   Think about how two people can rank the same items differently.

2. 2.

   Why is the brute force method considered inefficient?

   Hint

   Consider how the number of comparisons grows as items increase.

3. 3.

   What is an inversion in ranking?

   • A pair of items in correct order
   • A pair of items that are swapped
   • A pair of items that are out of order

   Hint

   Think about pairs that don't follow the expected order.

4. 4.

   True or False: The brute force method has a time complexity of O(n log n).

   • True
   • False

   Hint

   Consider the efficiency of different methods.

5. 5.

   You have two rankings, R1 = [3, 1, 4, 2] and R2 = [4, 3, 2, 1]. Calculate how many inversions exist and detail the method used.

   Hint

   Count all misordered pairs.

6. 6.

   Create an algorithm to efficiently count inversions in an array of size n, and analyze its time complexity.

   Hint

   Think about merging sorted arrays.