GATE CSE 2003 | Question: 22 Self doubt

Question

The unusual $\Theta(n^2)$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the best case running time will _____.

---

In gate worst case was asked but i wanted to know the best case. 

The best case of insertion sort is O(n) when the list is already sorted but here i think best case will be O(nlogn) because here no matter what the binary search will be performed for every element. 

Can someone confirm?

Comments

If you use the binary search then the number of comparison = O(log n) ( here the number of comparisons got decreased) But the number of movements will be   = O(n).

then O(n) + O(log n) = O(n)

This we have to do  n-1 times then total time complexity will be  = O (n^2).

What if we use the double linked list then

The number of comparisons will be = O(n) 

And number movements = o(1) ( movement reduced) 

Total = O(n) + O(1) = O(n)

We have to perform this n-1 times then Time Complexity will be = O(n^2).

There will not be any change in time complexity.

---

Binary search will find the location where the next element will be placed. For n locations to find it will be $O(nlogn)$ but we can't reduce the number of shifts. Every time a location is found then we need to move rest of the elements from location found to end of the list. So this will be an overhead each time and will be counted in time complexity. So here time complexity will ve $O(n^2)$

---

Well since you are asking for the best case, then it depends on the implementation.

If suppose you are currently working on the $i^{th}$ index,

then before calling binary_search you may check whether (arr[i-1]<arr[i]). In this case it will be O(n).

Else if you call binary_search without checking then what you said is correct.

Answer 1

You may misunderstood how insertion sort works. For any sorted array, there is NO NEED of binary search not even full linear search. The position is already fixed in a sorted array. So inner loop is $\mathrm{O}(1)$ and the outer loop is $\mathrm{O}(n)$. So it turns out that $\mathrm{O}(n\times 1)=\mathrm{O}(n)$

So for any sorted array (the best case), the time complexity of the Insertion sort is $\mathrm{O}(n)$.

Note: Please check this animation of how actual insertion sort is performed.

If this array above was sorted like $1,2,3,4,5,6,7,8$, it would just iterate the array [$\mathrm{O}(n)$] while checking each value with the next one only once to fix its position [meaning the inner loop is $\mathrm{O}(1)$].

Comments

Nice!

Answer 2

I THINK YOU ARE THINKING CORRECT

IF WE CONSIDER THE SCENARIO OF SORTED ARRAY THE FOLLOWING IS OCCURING

Comments

Actually for sorted array (the best case), the complexity of the Insertion sort is $\mathrm{O}(n)$. For any sorted array, there is NO NEED of binary search.

Note: Please check this animation of actual insertion sort.

---

Here you can read it.