Let $A\left [ i \right ] : i=0, 1, 2, \dots , n-1$ be an array of $n$ distinct integers. We wish to sort $A$ in ascending order. We are given that each element in the array is at a position that is at most $k$ away from its position in the sorted array, that is, we are given that $A[i]$ will move to a position in $\left \{ i-k,i-k+1,\dots,i,\dots ,i+k-1,i+k \right \}$ after the array is sorted in ascending order. Suppose insertion sort is used to sort this array: that is, in the $i$ th iteration, $A[i]$ is compared with the elements in positions $A[i-1], A[i-2], \dots$ until one that is smaller is found and $A[i]$ is inserted after that element. Note that elements can be moved back when later insertions are made before them. Let $t(n)$ be the worst-case number of comparisons made by insertion sort for such inputs. Then,
- $t\left ( n \right ) = \Theta \left ( n^{2} \right )$
- $t\left ( n \right ) = \Theta \left ( n\: \log_{2}\:n \right )$
- $t\left ( n \right ) = \Theta \left ( nk\:\log\:k \right )$
- $t\left ( n \right ) = \Theta \left ( n\:\log_{2}\:k \right )$
- $t\left ( n \right ) = \Theta \left ( nk \right )$