We have an array of n integers A1, A2,..., A. We say a pair of indices...

 

Transcribed Image Text:

We have an array of n integers A1, A2,..., A. We say a pair of indices have an inversion if i < j and A, > Aj. Design an algorithm that counts the number of inversions in O(nlogn) time. 5.1 Write your algorithm as a pseudo-code and provide a few sentences describing your approach. 5.2 Write a recurrence for the worst-case running time of your algorithm, and solve it. You may use any method for solving the recurrence that we have discussed in class. Example 1. For example, in A = [1, 4, 2, 3, 1] the number of inversions is 5. which is for pairs (i, j) = [(2, 3). (2, 4), (2, 5), (3, 5), (4, 5)] We have an array of n integers A1, A2,..., A. We say a pair of indices have an inversion if i < j and A, > Aj. Design an algorithm that counts the number of inversions in O(nlogn) time. 5.1 Write your algorithm as a pseudo-code and provide a few sentences describing your approach. 5.2 Write a recurrence for the worst-case running time of your algorithm, and solve it. You may use any method for solving the recurrence that we have discussed in class. Example 1. For example, in A = [1, 4, 2, 3, 1] the number of inversions is 5. which is for pairs (i, j) = [(2, 3). (2, 4), (2, 5), (3, 5), (4, 5)]