Question 1 write an algorithm in pseudo-code that accepts an integer n and an unordered array of n integers. The algorithm should calculate the average of the numbers and then tell how many of the elements are above the average. Exactly how many additions are done in the algorithm and exactly how many comparisons are done. Question 2 The idea of binary search can be generalized into k-ary search by dividing an n-element sorted array into n/k sub-arrays. Devise a tenary search algorithm that first tests the element at position and then checks the element at 2n/3. This algorithm either discovers the target n element or reduces the array to one-third of the original size. Question 3 Lt f(no 56 and g m) 51x na. Which of the following statements are true? (T or F. No explanation needed.) 3. f(n) e 60 g(n)) 5. f(n) E o(g(n)) 6. f(n) E O(g(n)) 7. f(n) E n(g(n)) S. g (n) E n(f(n)) Question 4 Given a recurrence relation T(n) 3T(n/2) n2, T(1) 1. 1. Draw the first four levels of the recurrence tree 2. Solve the recurrence to find a formula for T(n)