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

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

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

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