Why is the time complexity of insertion sort not brought down even if we use binary sort for the comparisons? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:24:51Z https://cs.stackexchange.com/feeds/question/65568 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/65568 6 Why is the time complexity of insertion sort not brought down even if we use binary sort for the comparisons? Somenath Sinha https://cs.stackexchange.com/users/43638 2016-11-05T02:01:07Z 2016-11-27T22:53:42Z <p>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? </p> <p>Are any of my statements wrong assumptions?</p> <p><strong>Edit</strong> 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.?</p> https://cs.stackexchange.com/questions/65568/-/65572#65572 8 Answer by aelguindy for Why is the time complexity of insertion sort not brought down even if we use binary sort for the comparisons? aelguindy https://cs.stackexchange.com/users/208 2016-11-05T02:31:02Z 2016-11-05T02:31:02Z <p>For the $j^{th}$ element, you would do ~ $\log j$ comparisons and (in the worst case) ~$j$ shifts.</p> <p>Summing over $j$, you get</p> <p>$$\sum_{j = 1}^{n} (j + \log j) = \frac{n(n+1)}{2} + \log (n!) = O(n^2 + n \log n) = O(n^2)$$</p> <p>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.</p> https://cs.stackexchange.com/questions/65568/-/66584#66584 2 Answer by gnasher729 for Why is the time complexity of insertion sort not brought down even if we use binary sort for the comparisons? gnasher729 https://cs.stackexchange.com/users/17408 2016-11-27T22:53:42Z 2016-11-27T22:53:42Z <p>The "possible explanation" after the edit in the question is exactly correct. That's why the time complexity is not improved. </p> <p>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. </p> <p>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. </p>