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

ID: 3788165 • 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) for the best case the time will be omega(N).

for the average case it will be theta(N^2)

for the worst case it will be big-O(N^2).

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 points in the plane, where A[i] contains the coordina

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