Log In
0 votes

Observe that the while loop of the INSERTION-SORT procedure uses a linear search to scan (backward) through the sorted subarray $A[i\dots j-1]$ Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to $\Theta(n\ lg\ n)$?

in Algorithms 47 views
Using Binary-Search in Insertion Sort we can only reduce number of Comparisons,however number of swaps remains same.

$ #Comparisons$ = $\mathcal{O}(n\log(n))$

$ #Swaps$ = $\mathcal{O} (n^{2})$

So,time complexity = $Comparion + Swaps$ = $\mathcal{O}(n\log(n))$ + $\mathcal{O} (n^{2})$ = $\mathcal{O} (n^{2})$

1 Answer

0 votes

Although by using Binary search instead of using linear search, the search time for finding the correct position for the element will decrease (becomes $\Theta(log\ n)$) but the swaps that we need to do to create the place for inserting that element will not change. So the overall time complexity will not be effected.

Related questions

0 votes
0 answers
Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence $A$ is sorted, we can check the midpoint of the sequence against $v$ and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, ... iterative or recursive, for binary search. Argue that the worst-case running time of binary search is $\Theta (lg\ n)$.
asked Jun 26, 2019 in Algorithms akash.dinkar12 49 views
0 votes
1 answer
Consider the linear search again (see Exercise 2.1-3). How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in ‚-notation? Justify your answers.
asked Jun 25, 2019 in Algorithms akash.dinkar12 121 views
0 votes
0 answers
Consider the searching problem: Input: A sequence of $n$ numbers $A = \langle a_1, a_2,\dots a_n \rangle$ and a value $v$ Output: An index $i$ such that $v=A[i]$ or the special value NIL if $v$ does not appear in $A$. Write ... sequence, looking for $v$. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
asked Jun 25, 2019 in Algorithms akash.dinkar12 54 views
0 votes
1 answer
Use mathematical induction to show that when $n$ is an exact power of $2$, the solution of the recurrence $T(n) = \begin{cases} 2 \text{, if n=2, } \\2T(n/2)+n \text{, if n=$2^k$,for k >1} \end{cases}$ is $T(n) = n\ lg\ n$.
asked Jun 26, 2019 in Algorithms akash.dinkar12 107 views