Given an array A[p..r], consider the following recursive algorithm Max. Max(A,p,r) 1 if p=r 2 return A[P] 3 else 45678910q=(p+r)2a=Max(A,p,q)b=Max(A,q+1,r)ifabreturnaelsereturnb 1. (5pts) Run Max(A,1,4) on array A[1.4]=5,10,3,8. 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(=rp+1). 3. (4pts) Solve the recurrence relation to give a tight bound (using ) on the running time of algorithm Max. Show the details. You mav type "Theta" instead of " " and type "Omega" instead of