999 views
1 votes
1 votes

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?

2 Answers

1 votes
1 votes

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)$].

0 votes
0 votes

I THINK YOU ARE THINKING CORRECT

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

Related questions

26 votes
26 votes
3 answers
4
Kathleen asked Sep 25, 2014
7,741 views
Give the correct matching for the following pairs: $$\begin{array}{ll|ll}\hline \text{(A)} & \text{$O (\log n)$} & \text{(P)} & \text{Selection} \\\hline \text{(B)} & \t...