The Gateway to Computer Science Excellence
+1 vote
175 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 by Boss (36.5k points) | 175 views
+3

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

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

by Active (3.5k points)
+1
Nice!
0 votes

I THINK YOU ARE THINKING CORRECT

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

by (195 points)
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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,312 answers
198,342 comments
105,033 users