Why does Insertion sort take linear time in this case? Remove any 5 elements from a sorted array of n items and replace them with 5 new elements.
Why does running Insertion sort again on this array take linear O(n) time, I tried counting the number of swaps when running Insertion sort again, and noticed every element is shifted by at most 5 places(not sure why), I cannot get the intuition behind why this takes linear time?
Wouldn't the new elements affect the position of the unchanged items in the array as well?
Appreciate any explanation on this!
Count the number of times each of the 5 new element is moved in the array:
The areay is of length $n$, and thus each of the 5 elements move at most $n$ times. The place of all other elements is correct, and thus there is at most $5n$ swaps required to &quot;correct&quot; the array, hence $O(n)$ swaps.