Insertion sort and selection sort can both be viewed as decrease by one algorithms. This is true in spite of the fact that Levitin classifies selection sort as a brute force algorithm. Does this mean that Levitin is wrong in his classification? For both Insertion sort and SelectionSort, do the following.

(a) Explain how a problem of size (n 1) is extracted from a problem of size n.

(b) Calculate the asymptotic efficiency of the process of extracting the problem of size (n1).

(c) Explain how the problem of size (n 1) is solved.

(d) Explain how the solution from step 3c (for the problem of size (n 1)) is extended to construct a solution for the original problem of size n.

(e) Calculate the asymptotic efficiency of the process of extending the solution to the problem of size (n 1) to the solution of the problem of size n.