3. Let A = A[1]... A[n] be an array of n distinct positive integers (the value of these integers could be very very larg

[answerhappygod]

3 Let A A 1 A N Be An Array Of N Distinct Positive Integers The Value Of These Integers Could Be Very Very Larg 1 (27.98 KiB) Viewed 48 times

3. Let A = A[1]... A[n] be an array of n distinct positive integers (the value of these integers could be very very large). An inversion is a pair of indices i and ; such that i <j but A> Aj For example in the array(30000, 80000, 20000, 40000, 10000), the pair i = 1 and j = 3 is an inversion because A[1] = 30000 is greater than A[3] = 20000. On the other hand, the pair * = 1 and j = 2 is not an inversion because A = 30000 is smaller than A[2] = 80000. In this array there are 7 inversions and 3 non-inversions, (a) Describe in one sentence the natural brite-force algorithm. (b) What is the complexity of the natural brute-force algorithm? (No explanation.) (e) Now give an O(n log ni)-time algorithm. (Hint: with some added bookkeeping this problem can be solved by an algorithm from class.)