Using the recursive algorithm

a. Suppose A = {7, 12, 8, 5, 9, 6} and consider the call Foo(A, 1, 6). List all recursive calls in the order that they are called. For each call, indicate the corresponding input values (including the values of and r) and the return value. Your first call will be Foo(A, 1, 6). b. Give a formal statement about what the output of algorithm Foo(A, , r) is. c. Write a recurrence relation to describe the running time of algorithm Foo, T (n), where n = r + 1 is the size of the input array A. d. Solve this recurrence relation to give a tight bound (with notation) on T (n).

Foo(A,1,r) // Input: Al..r) is an array of integers, l