12.8. Merging and Counting Inversions

Try these first

1. 1.

   Define what an inversion is in ranking.

   Hint

   Think about two items ranked differently.

2. 2.

   What is the time complexity of the brute force method for counting inversions?

   Hint

   Consider how many comparisons are made.

3. 3.

   What condition defines an inversion in two ranking orders?

   • When they are identical
   • When they are reversed
   • When they are in the same order

   Hint

   Think about pairs and their comparisons.

4. 4.

   Is counting inversions in a ranking system important for recommendation systems?

   • True
   • False

   Hint

   Consider how recommendations are determined based on user preferences.

5. 5.

   Given an array of movie rankings [4, 3, 2, 1], how many inversions does it contain? Illustrate your reasoning step by step.

   Hint

   List and compare each possible pair.

6. 6.

   Design an algorithm to count inversions in an array and analyze its time complexity.

   Hint

   Focus on iterating through merged arrays to count crossing conditions.