Given an array A[p..r], consider the following recursive algorithm Max. Max(A,p,r) 12345678910ifp==rreturnA[p]elseq=(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 may type "Theta" instead of " " and type "Omega" instead of