Page 1 of 1
Let A[1,..., n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i,j) is called a reverse pai
Posted: Sat Feb 19, 2022 3:21 pm
by answerhappygod
- Let A 1 N Be An Array Of N Distinct Numbers If I J And A I A J Then The Pair I J Is Called A Reverse Pai 1 (182.41 KiB) Viewed 40 times
Let A[1,..., n] be an array of n distinct numbers. If i < j and A
> A[j], then the pair (i,j) is called a reverse pair for A. (a) List the five reverse pairs of the array A [2, 3, 8, 6, 1]. (b) What is the relationship between the running time of INSERTION_SORT and the number of reverse pairs in the input array? Justify your answer. (c) Modify MERGE_SORT in order to give an algorithm which determines the number of reverse pairs in an array of n numbers in O(n log n) run time. Fully explain your algorithm and also justify why your algorithms satisfies the required time complexity bound.