Q3 and Q4

I will give a like

3. Give a big- estimate for each of the following recurrence relations. Show your work. (Hint: You should use the Master Theorem for the first three, but it can't be applied to part (d) - think about why). a. T(n)=T(n/3)+5 b. T(n)=2T(n/2)+4n2 c. T(n)=8T(n/4)+5n+2 d. T(n)=T(n2)+n 4. (Adapted from Exercise 2.3-7 in the textbook) Write pseudocode or Python code for a (nlgn) time algorithm that, given an array A of n distinct integers and another integer x, determines whether or not there exist two distinct elements in A whose sum is exactly x. Explain informally why your algorithm is (nlgn)-time. You may use calls to the Merge-Sort and/or BinarySearch algorithms as part of your pseudocode (you don't have to write out the code for Merge Sort or Binary Search). Your algorithm should return True or False. (Hint: Let p be the smallest element of A, r be the largest element of A, and z be any other element. If p+rx, what does that say about z+r ?)