a$)$Let n $=100.$

b$)$ Calculate the Average$-$case A$($n$)$ as we derived in class.

c$)$Let bound be an integer $($choose a large number$).$

d$)$ Let tot$-$number$-$steps $=0($accumulates total number of

e$)$ Generate a sequence of n integers $($positive and negative as well$)$ using a random number generator where the numbers of the sequence are between $0$ and bound. Call Insertion$-$Mod $()$ using this sequence and add the number of steps returned by this algorithm to tot$-$number$-$steps.

f$)$ Repeat steps e $100,000$ times $($i$.$e$.,$ generate $100,000$ random sequences and update tot$-$number$-$steps$).$

g$)$ Calculate the real average of algorithm A$10$ and let this number be A$2($n$).$

$$

$$

Repeat steps a$)-$thru g$)$ for the following values of n$,$ n$=\{100,500,1000,2500,3000,3500\}.$

You final output should look like: