1. Consider the following pseudocode for insertion-sort algorithm.The algorithm sorts an arbitrary array A[0..n − 1] of nelements.

void ISORT (dtype A[ ], int n) { int i, j; for i = 1 to n – 1 {     //Insert A[i] intothe sorted part A[0..i – 1]     j = i;     while (j > 0 andA[j] < A[j – 1]) {         SWAP (A[j], A[j –1]);         j = j – 1 }     } }

1. Illustrate the algorithm on the following array by showing eachcomparison/swap operation. What is the total number of comparisonsmade for this worst-case data?

A = (5, 4, 3, 2, 1)

1. Write a recursive version of this algorithm.

1. Let f(n) be the worst-case number of key comparisons made bythis algorithm to sort n elements. Write a recurrence equation forf(n). (Note that the sequence of comparisons are exactly the samefor both non-recursive and recursive versions. But, you may find itmore convenienet to write the recurrence for the recursiveversion.)

1. Find the solution for f(n) by repeated substitution.

1. Consider the bubble-sort algorithm described below.

void bubble (dtype A[ ], int n) { int i, j; for (i = n − 1; i > 0; i −−)        //Bubble max ofA[0..i] down to A[i].     for (j = 0; j         if (A[j] > A[j + 1])SWAP(A[j], A[j + 1]); }

1. Analyze the time complexity, T(n), of the bubble-sortalgorithm.

1. Rewrite the algorithm using recursion.

1. Let f(n) be the worst-case number of key-comparisons used bythis algorithm to sort n elements. Write a recurrence for f(n).Solve the recurrence by repeated substitution (i.e, iterationmethod).