Problem 5 (20 points) We have an array of integers 1, 2, ..., . We say a pair of indices have an inversion

if . Design an algorithm that counts the number of inversions in ( log) 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 = [1, 4, 2, 3, 1] the number of inversions is 5. which is for pairs (, )

= [ (2, 3), (2, 4), (2, 5), (3, 5), (4, 5) ]

oblem 5 (20 points) We have an array of n integers A1,A2,,An. We say a pair of indices have an inversion if iAj. 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)]