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

Question

Let A[1..n] be an array of n distinct numbers, (i, j) is called an inversion of A if i A[j] (note that I have used to denote an inversion in class. Since I used (i, j) here, either notation is acceptable for this assignment). 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) |. Here we are asking for the tight upper-bound, not in asymptotic notations. In other words, we are asking for the smallest upper-bound as a function of n.

Explanation / Answer

Ans :

In insertion sort, every time the inner loop is executed for eliminating one inversion.It is given that no of inversions for array A is inversion(A) and after sorting i.e. for moving every element in in its correct place, all inversions eliminates.Therefore, innerloop needs to be executed for exactly inversion(A) times. since the execution of outer loop is n times, the running time is O(n + inversion(A)).

Ans : All inversions are:-

(9,8), (8,7), (9,7), (9,3), (8,3), (7,3), (9,4), (8,4), (7,4), (9,5), (8,5), (7,5)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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