1
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ You probably meant bubble sort. Insersion sort adds the elements using binary search one at a time. $\endgroup$
    – nir shahar
    Apr 23 at 16:26
  • 1
    $\begingroup$ no, insertion sort is used in the question, it does not use the binary search version $\endgroup$
    – user624
    Apr 23 at 16:41
2
$\begingroup$

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 "correct" the array, hence $O(n)$ swaps.

$\endgroup$
3
  • $\begingroup$ but even the unchanged elements swapped more than once during the re-sort? I tried this example 123456789 --> 193250709, although I am not sure what example would require the worst case 5n swaps? $\endgroup$
    – user624
    Apr 23 at 16:42
  • $\begingroup$ Every unchanged element will swap only with one of the 5 new elements, because it was in a correct order when compared to any other old element (prove this statement formally). Therefore, the total number of swaps can be counted only using the 5 new elements $\endgroup$
    – nir shahar
    Apr 23 at 17:10
  • $\begingroup$ 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. $\endgroup$
    – nir shahar
    Apr 23 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.