Given an array A[p..r], consider the following recursive algorithm Max. Max(A, p, r) return A[p] 1 if p == r 2 3 else 4 ST 5 6 7 9 a == = =L(p + + r) / 2 Max (A, p, q) b Max (A, q+1, r) = if a b 00 8 return a 9 else 10 return b 1. (5pts) Run Max (A, 1, 4) on array A[1..4] = . What will be the output? Show all the recursive calls to Max along with the corresponding return values. 2. (3pts) Write a recurrence relation describing the running time of algorithm Max (A, p, r) in terms of n (= r -p + 1). 3. (4pts) Solve the recurrence relation to give a tight bound (using e) on the running time of algorithm Max. Show the details. You may type "Theta" instead of "e" and type "Omega" instead of ".".