Analysis of Algorithm course

Please print or write neatly

5. Algorithm Design (20 points) Input: array A contains n distinct numbers from 1 to n, in arbitrary order. Output: number of inversions (defined as the number of pair(i, j) of array indices with i A[j]). (a) (5 points) What array with elements from the set {1, 2, ..., n} has the most inversions? How many does it have? (b) (15 points) Create an algorithm using divide-and-conquer approach that determines the number of inversions in any permutation on n elements in (nlgn) worst-case time (Hint: modify the merge sort)