Give asymptotically tight big-O bounds for T(n) in each of the following recurrences. Justify your solution by naming the master method case, by iterating the recurrence, or by using the substitution method. a. T(n) = T(n - 2) + 1 b. T(n) = 2T(n/2) + n lg^2 n c. T(n) = 9T(n/4) + n^2 d. T(n) = 3T(n/2) + n e. T(n) T(n/2 + n^0.5) + n Consider a set S of n greaterthanorequalto 2 distinct numbers all greater than zero in unsorted order. For each of the problems below: Give an algorithm to determine two distinct numbers x and y in the set S that satisfy the condition(s) of the problem. Your algorithm must be specified using pseudocode in the style of the text. You must justify that your algorithm has the requested run time. a. in O(n lg n) time, determine x, y elementof S such that x notequalto y and |x - y| lessthanorequalto lw - zl for all w, z elementof S such that w notequalto z. b. in O(n) time, determine x, y elementof S such that |x - y| greaterthanorequalto lw - zl for all w, z elementof S for all w, z elementof S such that w notequalto z