Problem 3 . Suppose elements a[i] and a[i+k] are in the wrong order and we swap them. Prove that this will remove at least 1 inversion but at most 2k − 1 inversions. (This is textbook problem 7.3.) Further explain why both the lower bound of 1 and the upper bound of 2k − 1 can be attained for any i, k, where k > 0
To prove that one inversion is required at 2k-1 inversion is
shown as follows:
The inversion that existed between A[i] and A[i+k] is removed. This
shows at least one inversion is removed. Now let's consider
A[i],A[i+1],…,A[i+k−1],A[i+k], Suppose A[i] is greater than
A[i+1],…,A[i+k] and A[i+k] is smaller than A[i],…,A[i+k−1]. In this
case, by swapping A[i] and A[i+k], we fix 2k−1 inversions (−1 is
that A[i] greater than A[i+k] and A[i+k] smaller than A[i] points
to the same inversion).
Another way to think about 2k−1 is that for each of the k−1
elements A[i+1],A[i+2],…,A[i+k−1], at most two inversions can be
removed by exchange. For instance, for A[i+1], two inversions are
A[i] and A[i+1], and A[i+1] and A[i+k] (i.e. for sequence 10,4,3,
by swapping 10 and 3, we remove inversion {10,4} and {4,3}). Thus,
a maximum of 2(k−1)+1=2k−1.
--------------------------------------------------Please Upvote-------------------------------------------------------------------------------
Get Answers For Free
Most questions answered within 1 hours.