Problem $(1)$ implies the following fact: given sorted A$[1]$ A$[$k$]$ and x$,$ we

can simulate binary search to find in O$($log k$)$ time the index in A where x

belongs.

Now, consider the following modified version of insertion sort $($no need to

provide any pseudo$-$code$)$: for $2<=$ j $<=$ n$,$ to insert the key A$[$j$]$ among

A$[1]<=$ A$[2]<=<=$ A$[$j$-1],$ do a binary search in A$[1]$ A$[$j $1]$ first to find

the correct position for A$[$j$],$ and then insert it$,$ so that we now have A$[1]<=$

A$[2]<=<=$ A$[$j$-1]<=$ A$[$j$].$

Suppose the modified algorithm is run on an array of size n$.$

$($b$)$ In the worst case, over the entire run of the algorithm, i$.$e$.,$ from

start to finish, what is the total number of comparisons $($between

keys$)$ done $?$ Give a $\backslash$theta bound and justify.