# Proof for time complexity of Insertion (k-proximate) Sort equals O(nk)

The following is the definition for Proximate Sorting given in my paper:

An array of distinct integers is k-proximate if every integer of the array is at most k places away from its place in the array after being sorted, i.e., if the $$i$$th integer of the unsorted input array is the $$j$$th largest integer contained in the array, then $$|i − j| ≤ k$$.

The following is the proof for time complexity of k-proximate insertion sort:

To prove $$O(nk)$$, we show that each of the n insertion sort rounds swap an item left by at most $$O(k)$$.

In the original ordering, entries that are $$≥ 2k$$ slots apart must already be ordered correctly: indeed, if $$A[s] > A[t]$$ but $$t − s ≥ 2k$$, there is no way to reverse the order of these two items while moving each at most $$k$$ slots. This means that for each entry $$A[i]$$ in the original order, fewer than $$2k$$ of the items $$A[0], . . . , A[i−1]$$ are less than $$A[i]$$. Thus, on round $$i$$ of insertion sort when $$A[i]$$ is swapped into place, fewer than $$2k$$ swaps are required, so round $$i$$ requires $$O(k)$$ time.

My problem with the proof is this line : "This means that for each entry A[i] in the original order, fewer than 2k of the items $$A[0], . . . , A[i−1]$$ are less than A[i]". The preceding statements just proved that $$t-s < 2k$$, otherwise the elements are sorted (as elements with distance greater than $$2k$$ cannot be swapped.) Isn't the correct statement : "This means that for each entry A[i] in the original order, fewer than 2k of the items $$A[0], . . . , A[i−1]$$ are greater than A[i]"?

Yes if you sort the array in ascending order you are right it should be less than $$2k$$ elements in $$A[0],...,A[i-1]$$ are greater than $$A[i]$$. A simple array were the statement w is wrong ($$k = 1$$):
$$[1,2,3,4]$$