search
Log In
1 vote
351 views

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?

in Algorithms 351 views
4

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.

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

2 Answers

1 vote

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

1
Nice!
0 votes

I THINK YOU ARE THINKING CORRECT

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

0

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.

0

Here you can read it.

Related questions

42 votes
2 answers
1
8.1k views
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 worst case running time will remain $\Theta(n^2)$ become $\Theta(n (\log n)^2)$ become $\Theta(n \log n)$ become $\Theta(n)$
asked Sep 16, 2014 in Algorithms Kathleen 8.1k views
54 votes
9 answers
2
10.4k views
In a permutation \(a_1 ... a_n\), of $n$ distinct integers, an inversion is a pair \((a_i, a_j)\) such that \(i < j\) and \(a_i > a_j\). What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of \(1. . . n\) with at most $n$ inversions? \(\Theta(n^2)\) \(\Theta(n\log n)\) \(\Theta(n^{1.5})\) \(\Theta(n)\)
asked Apr 24, 2016 in Algorithms jothee 10.4k views
52 votes
10 answers
3
8.9k views
In a permutation \(a_1 ... a_n\), of n distinct integers, an inversion is a pair \((a_i, a_j)\) such that \(i < j\) and \(a_i > a_j\). If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of \(1. . . n\)? \(\frac{n(n-1)}{2}\) \(\frac{n(n-1)}{4}\) \(\frac{n(n+1)}{4}\) \(2n[\log_2n]\)
asked Sep 17, 2014 in Algorithms Kathleen 8.9k views
0 votes
1 answer
4
232 views
Rewrite the INSERTION-SORT procedure to sort into non-increasing instead of non-decreasing order.
asked Jun 25, 2019 in Algorithms akash.dinkar12 232 views
...