6
$\begingroup$

There are two factors that decide the running time of the insertion sort algorithm : the number of comparisons, and the number of movements. In the case of number of comparisons, the sorted part (left side of $j$) of the array is searched linearly for the right place of the $j^{th}$ element. If instead, we use a binary search, then the time complexity of finding a place for the $j^{th}$ element comes down from $\operatorname{O}(n)$ to $\operatorname{O}(\log n)$. So, for all the $n$ elements, the time complexity for comparisons becomes $\operatorname{O}(n \log n)$. Even so, the number of movements is still going to take $\operatorname{O}(n)$ time, and the total time complexity isn't brought down and remains $\operatorname{O}(n^2)$. Why is that?

Are any of my statements wrong assumptions?

Edit Can a possible explanation be: the total time complexity isn't brought down and remains $\operatorname{O}(n^2)$. This is because to search an element (using binary search) it takes $\operatorname{O}(\log n)$ time, and to move the elements it takes $\operatorname{O}(n)$ time. Total cost is $\operatorname{O}(\log n)+\operatorname{O}(n)=\operatorname{O}(n)$ time. To do this for $n-1$ elements, it takes $n(n-1)=\operatorname{O}(n^2)$ time.?

$\endgroup$
8
$\begingroup$

For the $j^{th}$ element, you would do ~ $\log j$ comparisons and (in the worst case) ~$j$ shifts.

Summing over $j$, you get

$$ \sum_{j = 1}^{n} (j + \log j) = \frac{n(n+1)}{2} + \log (n!) = O(n^2 + n \log n) = O(n^2) $$

The idea is that the linear work of shifting trumps the logarithmic work of comparing. You end up doing less comparisons, but still a linear amount of work per iteration. So the complexity does not change.

$\endgroup$
  • $\begingroup$ This explains it perfectly. Thank you.. $\endgroup$ – Somenath Sinha Nov 5 '16 at 2:33
  • $\begingroup$ Also, can I state it as: The total time complexity isn't brought down and remains $\operatorname{O}(n^2)$. This is because to search an element (using binary search) it takes $\operatorname{O}(\log n)$ time, and to move the elements it takes $\operatorname{O}(n)$ time. Total cost is $\operatorname{O}(\log n)+\operatorname{O}(n)=\operatorname{O}(n)$ time. To do this for $n-1$ elements, it takes $n(n-1)=\operatorname{O}(n^2)$ time. $\endgroup$ – Somenath Sinha Nov 5 '16 at 2:36
  • 1
    $\begingroup$ @SomenathSinha yes, but because in this case we know that linear work sums up to be quadratic (the sum over $j$ ends up being quadratic), one would have to be careful for other kinds of functions that sum up differently. But in this case you can say that $O(j) + O(\log j) = O(j)$ and that sums up to $O(n^2)$. $\endgroup$ – aelguindy Nov 5 '16 at 2:49
2
$\begingroup$

The "possible explanation" after the edit in the question is exactly correct. That's why the time complexity is not improved.

On the other hand, unless the array is already mostly sorted, or if the array is very small, using binary search to find where to insert an array element is very likely to make the sorting almost twice as fast.

On the other hand, for large n where sorting an array using insertion sort is unacceptably slow, making it twice as fast still leaves it unacceptably slow.

$\endgroup$

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.