TIFR CSE 2021 | Part B | Question: 15

Question

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,

• A. $t\left ( n \right ) = \Theta \left ( n^{2} \right )$
• B. $t\left ( n \right ) = \Theta \left ( n\: \log_{2}\:n \right )$
• C. $t\left ( n \right ) = \Theta \left ( nk\:\log\:k \right )$
• D. $t\left ( n \right ) = \Theta \left ( n\:\log_{2}\:k \right )$
• E. $t\left ( n \right ) = \Theta \left ( nk \right )$

Comments

The short-answer is $O(nk)$ I suppose… For Insertion Sort scan over $N$ elements, in each iteration the element we’ve to insert in the already sorted array the left of the to-be inserted element, should need at most $O(k)$ swaps as said in the question.
There’re subtle variations were it might be confusing such as the element needs to-be shifted to the right, but it is taken care of the element in the right(ah my brain)…

Answer 1

Let me recall that in insertion sort we have two parts in the array. First one is where element are sorted and second one is in which elements are not sorted. In each step but we do we pick an element (starting element) from the unsorted array and put it into the right place in the sorted array part by comparisons. To insert an element into its exact position elements from the sorted part might need to be shift.

Coming to the question we are promised that each element is at most k distance from its actual position. Now when an element (Say x) will be picked from the unsorted part. To insert x into its correct position we only need to compare it with O(k) many elements and also need to move/shift at most O(k) elements (as given in the question statement that element is k distance away from its actual position). Now to insert n elements intio their right position it will take O(nk) time.