Note: S is just an array containing n elements; For this question S[4] = {a,b,c,d}, where n = 4

Please provide a detailed and legible explanation. Thank you

1. Consider the algorithm formulation (simple recursive) for Insertion Sort discussed in class. a. Write the problem, inputs, outputs, and algorithm description using the Insert subroutine b. Now consider Insert subroutine which is used in Insertion Sort Algorithnm. i) Write the problem, inputs, outputs, and algorithm description for Insert subroutine. ii) Draw a decision/comparison tree for your Insert Subroutine Algorithm when S is (a, b, c, d). Note that (a, b, c) is sorted. ii) Let W(n) denote the number of pair-wise comparisons of elements in Srequired by the Insert Subroutine Algorithm in the worst case. What is Wn) ? Algorithm when S is (a, b, c, d). Sort Algorithm in the worst case. Write a recurrence relation for Win) for your algorithm and c. Draw a partial comparison tree (containing a reasonable number of nodes) for your Insertion Sort d. Let W) denote the number of pair-wise comparisons of elements in S required by the Insertion solve it to determine Wn)