Proof for time complexity of Insertion (k-proximate) Sort equals O(nk)
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]$$
However is you sort in descending order it's the other way around.
But you have a good point because this seems to imply that ascending is meant...

&quot;indeed, if A[s] &gt; A[t] but t − s ≥ 2k, there is no way to reverse the order of these two items&quot;