Statement of question is [this](https://www.geeksforgeeks.org/counting-inversions/).↵
I read an approach to this question on stack overflow and it is :↵
↵
1. Merge sort array A and create a copy (array B)↵
↵
2. Take A[1] and find its position in sorted array B via a binary search. The number of inversions for this element will be one less than the index number of its position in B since every lower number that appears after the first element of A will be an inversion.↵
↵
2a. accumulate the number of inversions to counter variable num_inversions.↵
↵
2b. remove A[1] from array A and also from its corresponding position in array B↵
rerun from step 2 until there are no more elements in A.↵
↵
Here’s an example run of this algorithm. Original array A = (6, 9, 1, 14, 8, 12, 3, 2)↵
↵
1: Merge sort and copy to array B↵
↵
B = (1, 2, 3, 6, 8, 9, 12, 14)↵
↵
2: Take A[1] and binary search to find it in array B↵
↵
A[1] = 6↵
↵
B = (1, 2, 3, 6, 8, 9, 12, 14)↵
↵
6 is in the 4th position of array B, thus there are 3 inversions. We know this because 6 was in the first position in array A, thus any lower value element that subsequently appears in array A would have an index of j > i (since i in this case is 1).↵
↵
2.b: Remove A[1] from array A and also from its corresponding position in array B (bold elements are removed).↵
↵
A = (6, 9, 1, 14, 8, 12, 3, 2) = (9, 1, 14, 8, 12, 3, 2)↵
↵
B = (1, 2, 3, 6, 8, 9, 12, 14) = (1, 2, 3, 8, 9, 12, 14)↵
↵
3: Rerun from step 2 on the new A and B arrays.↵
↵
A[1] = 9↵
↵
B = (1, 2, 3, 8, 9, 12, 14)↵
↵
9 is now in the 5th position of array B, thus there are 4 inversions. We know this because 9 was in the first position in array A, thus any lower value element that subsequently appears would have an index of j > i (since i in this case is again 1). Remove A[1] from array A and also from its corresponding position in array B (bold elements are removed)↵
↵
A = (9, 1, 14, 8, 12, 3, 2) = (1, 14, 8, 12, 3, 2)↵
↵
B = (1, 2, 3, 8, 9, 12, 14) = (1, 2, 3, 8, 12, 14)↵
↵
Continuing in this vein will give us the total number of inversions for array A once the loop is complete.↵
↵
Step 1 (merge sort) would take O(n * log n) to execute. Step 2 would execute n times and at each execution would perform a binary search that takes O(log n) to run for a total of O(n * log n). Total running time would thus be O(n * log n) + O(n * log n) = O(n * log n).↵
↵
My question is in case of repeating elements like [4,7,4] what if we modify binary search for finding first occurrence of that element and using erase in vectors to erase the element. What will be the time complexity then ? According to me it is still O(nlogn).↵
↵
Thanks in advance.
I read an approach to this question on stack overflow and it is :↵
↵
1. Merge sort array A and create a copy (array B)↵
↵
2. Take A[1] and find its position in sorted array B via a binary search. The number of inversions for this element will be one less than the index number of its position in B since every lower number that appears after the first element of A will be an inversion.↵
↵
2a. accumulate the number of inversions to counter variable num_inversions.↵
↵
2b. remove A[1] from array A and also from its corresponding position in array B↵
rerun from step 2 until there are no more elements in A.↵
↵
Here’s an example run of this algorithm. Original array A = (6, 9, 1, 14, 8, 12, 3, 2)↵
↵
1: Merge sort and copy to array B↵
↵
B = (1, 2, 3, 6, 8, 9, 12, 14)↵
↵
2: Take A[1] and binary search to find it in array B↵
↵
A[1] = 6↵
↵
B = (1, 2, 3, 6, 8, 9, 12, 14)↵
↵
6 is in the 4th position of array B, thus there are 3 inversions. We know this because 6 was in the first position in array A, thus any lower value element that subsequently appears in array A would have an index of j > i (since i in this case is 1).↵
↵
2.b: Remove A[1] from array A and also from its corresponding position in array B (bold elements are removed).↵
↵
A = (6, 9, 1, 14, 8, 12, 3, 2) = (9, 1, 14, 8, 12, 3, 2)↵
↵
B = (1, 2, 3, 6, 8, 9, 12, 14) = (1, 2, 3, 8, 9, 12, 14)↵
↵
3: Rerun from step 2 on the new A and B arrays.↵
↵
A[1] = 9↵
↵
B = (1, 2, 3, 8, 9, 12, 14)↵
↵
9 is now in the 5th position of array B, thus there are 4 inversions. We know this because 9 was in the first position in array A, thus any lower value element that subsequently appears would have an index of j > i (since i in this case is again 1). Remove A[1] from array A and also from its corresponding position in array B (bold elements are removed)↵
↵
A = (9, 1, 14, 8, 12, 3, 2) = (1, 14, 8, 12, 3, 2)↵
↵
B = (1, 2, 3, 8, 9, 12, 14) = (1, 2, 3, 8, 12, 14)↵
↵
Continuing in this vein will give us the total number of inversions for array A once the loop is complete.↵
↵
Step 1 (merge sort) would take O(n * log n) to execute. Step 2 would execute n times and at each execution would perform a binary search that takes O(log n) to run for a total of O(n * log n). Total running time would thus be O(n * log n) + O(n * log n) = O(n * log n).↵
↵
My question is in case of repeating elements like [4,7,4] what if we modify binary search for finding first occurrence of that element and using erase in vectors to erase the element. What will be the time complexity then ? According to me it is still O(nlogn).↵
↵
Thanks in advance.
