3. Selection Sort can be thought of as a recursive algorithm as follows: Find the largest element and put it at the end of the list (to be sorted). Recursively sort the remaining elements. That is, F(n) = F(n-1) + some operations. a. Write down the recursive version of Selection Sort in psuedocode. b. Derive a recurrence for the exact number of comparisons that your algorithm uses. c. Use the iteration method to solve the recurrence. Simplify as much as possible.

4. For every pass (the moment for the outer loop in the program), show the result of the whole array when the original sequence is {6, 3, 2, 5, 7, 9, 4, 3, 1} if it is using a. Bubble sort b. Insertion sort c. Selection sort (hint: you could use the program to run the above sequence and then display the result of each pass)

1. Use the formal definitions of Big O (not the Limit Rule) to establish the following statements. In each case you need to specific values of the constants (e.g., cl, c2, n0) you used to satisfy the conditions, and show how you arrived at these values. (There are many potentially correct choices. Explaining your work is thus essential for full credit.) (a) 4n2 +4n12- O(n2-4n+8) (b)2n3-3n217n- (n) (c) n210n lg n O(n). (Hint: Find n0 such that Ig nn, for all n n0.) 2 Rank the following functions in increasing order of asymptotic growth rate. For functions that are asymptotically equivalent, group them together. You do not need to prove your order getting partial credit. ing, but you may supply explanations for the purpose of A(n)500n fa(n)17n(22), (n)23em) fs(n)5g10lgn, fo(n)201g(n2) fo(n) = 41%, n