Let A[1..n] be an array of n distinct numbers, (i, j) is called an inversion of

ID: 3792154 • Letter: L

Question

Let A[1..n] be an array of n distinct numbers, (i, j) is called an inversion of A if i A[j] The inversion number of A, denoted by inversion(A), is the total number of inversions of array A. Express the running time of sorting A using insertion sort. Your answer should use asymptotic notations involving n and inversion(A). Justify your answer. List all the inversions of the following array. Suppose you have an array A with n elements. Array B is obtained from array A by deleting two elements and inserting them back (to some positions) in array A. Find an upper-bound on |inversion(A) - inversion(B)|.

Explanation / Answer

1 2 3 4 5 6

9 8 7 3 4 5

Maximum will be reached when inversion(A) is max while inversion (B) is min. This can happen when maximum two elements of A are on leftmost side and they are placed at rightmost side in B. So, A[1] = n. A[2] = n-1. B[n-1] = n-1 B[n] = n. This makes | inversion(A) - inversion(B) | = 2n-1

Navigate

Let A[1..n] be an array of n distinct numbers, (i, j) is called an inversion of

Let A[1..n] be an array of n distinct numbers. (i, j) is called an inversion of

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

Let A[1..n] be an array of n distinct numbers, (i, j) is called an inversion of

Question

Explanation / Answer

Related Questions

Navigate