# 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!

• You probably meant bubble sort. Insersion sort adds the elements using binary search one at a time. Apr 23, 2021 at 16:26
• no, insertion sort is used in the question, it does not use the binary search version Apr 23, 2021 at 16:41

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 "correct" the array, hence $$O(n)$$ swaps.
• The worst case would be slightly less than $5n$. The $5n$ I gave is just a bound to show this is indeed linear time. You might be able to think of a slightly better bound than that, but it would still be linear in $n$. Also, a simple example that reaches a high number of swaps is when the new elements are placed at the end of the array, but their actual place is at the beggining of it (they are smaller than every other element in the array). This would ensure at least $5(n-5)$ swaps. Apr 23, 2021 at 17:13