(20) Let A[1…n] be an array of n distinct numbers. If i < j and A[i] > A[j], the

Question

(20) 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 an inversion of A.

(2) List the five inversions of the array A = {2, 3, 8, 6, 1}

(3) What array with elements from the set {1, 2, …, n} has the most inversions?

(10) Design an algorithm that determines the number of inversions in any permutation on n elements in (n log n) worst-case time.

(5) Suppose that the elements of A form a uniform random permutation of {1, 2, …, n}, what is the expected number of inversions?

Explanation / Answer

1. Inversions of the array A = {2, 3, 8, 6, 1} are (1, 5), (2, 5), (3, 4), (3, 5), and (4, 5) .

2. Because inversion is comparison of each index to next indices, So, if the array is reverse sorted, number of inversions will be maximum.

3. We can use divide and conquer approach to solve this problem. We can divide the array into halves. For this division process, the running time is (logn).

For each divided array we need to count the inversions, for counting inversions the running time is (n).

So, total running time is (n log n).

4. Expected number of inversion if array is reverse sorted is equal to number of ways to choose 2 distinct integers from the set. i.e. nC2 = n(n-1) / 2

As array is random , so the probability of getting the set choosen is half.

So expected number of inversions in reverse sorted array = n(n-1) / 2 * ½ = n(n-1) / 4

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.