edited by
592 views
2 votes
2 votes
Suppose in an array A[] , we exchange elements A[i] and A[i+k] , which were originally out of order
A) at least 1 and at most 2k-1 inversions are removed
B) at least 2 and at most 2k inversions are removed
C)at least 0 and at most k  inversions are removed
D) none
edited by

1 Answer

Best answer
2 votes
2 votes
Elements 5 4 3 2 1
Inversions 4 3 2 1 0

Total Inversions = 4+3+2+1+0 =10

  1. for minimum, let k=1 , swap(a[0],a[0+1])
Elements 4 5 3 2 1
Inversions 3 3 2 1 0

Total Inversions = 3+3+2+1+0 =9

difference =1

2. now, let k= 2, swap(a[0],a[0+2])

Elements 3 4 5 2 1
Inversions 2 2 2 1 0

Total Inversions = 2+2+2+1+0 =7

difference =3

From 1 and 2:

Option A satisfies.

selected by
Answer:

Related questions

1 votes
1 votes
1 answer
1
Hradesh patel asked Jan 27, 2017
371 views
plz explain ?? i got O(nlogn)
0 votes
0 votes
2 answers
2
1 votes
1 votes
1 answer
3
amit166 asked Jan 5, 2023
283 views
Time complexity=$\sum_{i=1}^{n}[\log (\frac{n}{i})] is$