Cormen Edition 3 Exercise 2.3 Question 6 (Page No. 39)

0 votes
47 views

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

0
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
1
49 views
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)$.
0 votes
1 answer
2
121 views
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.
0 votes
0 answers
3
54 views
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.
0 votes
1 answer
4
107 views
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$.