Register

GO Classes DPP | GATE CS, DA | Algorithms | Binary Search Insertion

225 views
2 2 votes

Suppose Binary Search is used in Insertion Sort to locate where the $i$th element should be inserted among the first $i-1$ elements.

What is the worst-case running time of this implementation?

  1. $\Theta(n^2)$
     
  2. $\Theta(n\log n)$
     
  3. $\Theta(n)$
     
  4. $\Theta(\log n)$

2 Answers

1 1 vote

Normally, Insertion Sort searches backward through the sorted portion to find the correct position.

Using Binary Search improves this search.

For the $i$th element, the insertion position can be found in: $\Theta(\log i)$ time.

It may therefore appear that the total complexity becomes: $\Theta(n\log n)$

But after finding the correct location, elements must still be shifted to make space.

In the worst case, inserting the $i$th element may require shifting: $i-1$ elements.

$\therefore T(n)=1+2+3+\cdots+(n-1)$

$\Rightarrow T(n)=\frac{n(n-1)}{2}$

Hence,

$T(n)=\Theta(n^2)$

Binary Search reduces the number of comparisons needed to find the insertion position, but it does not eliminate the linear number of shifts required for each insertion.

0 0 votes
Using binary search to find the insertion location of the i-th element would not change the fact that we will still need to shift $\Theta(n)$ elements in each iteration in the worst case (reversed sorted array). Leaving the total runtime to be the same as before i.e $\Theta(n^2)$

Answer: A
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

3 3 votes
2 2 answers
253
253 views
GO Classes asked Aug 12
253 views
GO Classes DPP | GATE CS, DA | Algorithms | Identify Sort State
You are given an initial array:$[22,10,14,37,14,4,3]$For the following array, indicate which sorting algorithm could produce this state after an iteration has completed:$...
2 2 votes
2 2 answers
231
231 views
GO Classes asked Aug 12
231 views
GO Classes DPP | GATE CS, DA | Algorithms | Bubble Sort
Which algorithm-design strategies can reasonably describe Bubble Sort?Greedy Brute force Decrease-and-conquer Divide-and-conquer Dynamic programming
3 3 votes
2 2 answers
198
198 views
GO Classes asked Aug 12
198 views
GO Classes DPP | GATE CS, DA | Algorithms | Selection Sort
What effect does the initial ordering of the records have on the number of comparisons performed by standard Selection Sort?No effect Only a constant-factor difference Th...
2 2 votes
2 2 answers
184
184 views
GO Classes asked Aug 12
184 views
GO Classes DPP | GATE CS, DA | Algorithms | Bubble Sort
After the first complete pass of Bubble Sort on an array of size $n$, which element is guaranteed to be in its correct position?The smallest element The largest element A...