his problem relates to insertion sort $($see pseudocode below$).$

Use $1$ n as data for input of size n$.$ For example, n $123$ n $$

$2$ n $1$ is a specific input of size n$.$

When I say $$analyze the algorithm$,$ I want details of work done $($i$.$e$.$

expression$)$ in the worst case along with a $\backslash$theta bound on that.

$//$ To sort A$[1]...$ A$[$n$]$

insertion$-$sort $($A$[],$ n$)\{$

for j $=2$ to n $\{$

key $=$ A$[$j$]$;

$//$ insert A$[$j$]$ into the sorted sequence A$[1]...$ A$[$j$-1]$

i $=$ j$-1$;

while $(($i $>0)$ and $($A$[$i$]>$ key$))\{$

A$[$i$+1]=$ A$[$i$]$;

i $=$ i $-1$;

$\}//$ while

A$[$i$+1]=$ key;

$\}//$ for

$\}$

$($a$)$ Present a worst case input for the algorithm and analyze the complexity

of the algorithm.

Read the following before solving $($b$)$ through $($d$)$

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.

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

start to finish, what is the total number of times keys are moved $?$

Give a $\backslash$theta bound and justify.

$($d$)$ What is the worst case complexity of the entire sorting algorithm $?$

Justify.